647. Palindromic Substrings - Detailed Explanation
Problem Statement
Given a string s, return the number of palindromic substrings in it. A string is a palindrome if it reads the same backward as forward (e.g., "racecar"). A substring is a contiguous sequence of characters within the string.
-
Example 1: Input:
s = "abc"– Output:3
Explanation: The palindromic substrings are "a", "b", and "c". Each individual character is a palindrome of length 1. -
Example 2: Input:
s = "aaa"– Output:6
Explanation: The palindromic substrings are "a", "a", "a", "aa", "aa", "aaa". Here every possible substring is a palindrome.
Constraints: 1 <= s.length <= 1000. The string consists of lowercase English letters.
Hints to Solve the Problem
-
Brute Force All Substrings: Try generating all possible substrings of
sand check each one for palindrome properties. This is straightforward but very inefficient for large strings. -
Expand from Center: Notice that a palindrome expands symmetrically around its center. You can pick each index (and each gap between indices) as a potential center and expand outward to count palindromes, rather than checking every substring independently.
-
Use Dynamic Programming: Store results for substrings that have been checked. For example, use a 2D DP table
dp[i][j]indicating whethers[i:j+1]is a palindrome. This can save time by reusing previously computed results for inner substrings.
Approaches to Solve the Problem
Approach 1: Brute Force (Check All Substrings)
Idea: Generate every possible substring of s and test if it is a palindrome. We can use a helper function to check palindromicity by comparing the substring with its reverse, or by using two-pointer technique from both ends. Increment a counter for each substring that is a palindrome.
Complexity Analysis:
- Time Complexity: O(n^3) in the worst case. There are ~O(n^2) substrings and checking each substring for palindrome takes O(n) time, resulting in O(n^2) * O(n) = O(n^3). This is very slow for large n (e.g., n=1000 could mean ~10^9 checks).
- Space Complexity: O(1) auxiliary space (not counting the input and output), since we only use a few variables for counting and indices.
Python Code:
Java Code:
Discussion: The brute force approach is easy to understand but highly inefficient. It literally examines every substring. For a string of length n, there are n*(n+1)/2 possible substrings, and checking each one individually is costly. This approach will time out for larger input sizes (near the upper constraint). It’s mainly useful as a correctness check or a baseline.
Approach 2: Expanding Around Centers (Optimal Solution)
Idea: Instead of checking all substrings explicitly, we can expand around each possible center of a palindrome. A palindrome can have one center (odd-length palindromes, like "aba") or two centers (even-length palindromes, like "abba"). We iterate through the string, treating each index as a center and each pair of adjacent indices as a center, and expand outwards while the characters at both ends are equal. Each expansion that yields matching characters represents a palindromic substring.
Complexity Analysis:
-
Time Complexity: O(n^2) in the worst case. There are
2n - 1possible centers to consider (n single-character centers and n-1 between-character centers). For each center, in the worst case we might expand to the full length of the string (O(n) work per center), giving ~2n * O(n) = O(n^2) operations total. This is much more efficient than O(n^3), and for n up to 1000 it is very acceptable. -
Space Complexity: O(1) auxiliary space, since we only use a few pointers and counters. We do not need extra tables as in DP.
Python Code:
Java Code:
Discussion: This center-expansion approach efficiently counts palindromic substrings without explicitly generating them. For each character (and each gap between characters), we greedily expand outwards as long as we have a palindrome. Every time the expansion yields a match, that forms a palindromic substring. For example, in "aba", when centered at index 1 (the letter "b"), expanding out finds "aba". When centered between index 0 and 1 (between "a" and "b"), there's no palindrome longer than length 0, etc. By doing this for all centers, we count all palindromic substrings. This approach is optimal for this problem, given the constraints, and is simpler to implement than dynamic programming in this case.
Approach 3: Dynamic Programming (Using a DP Table)
Idea: Use a 2D dynamic programming table to track palindromic substrings. We create an n x n table dp, where dp[i][j] is True if the substring s[i...j] (inclusive) is a palindrome, and False otherwise. The table can be filled using the following logic:
- All single characters are palindromes (base case).
- A substring of length 2 is a palindrome if both characters are equal.
- For length > 2,
dp[i][j]is true ifs[i] == s[j]anddp[i+1][j-1]is true (meaning the inner substring is also a palindrome).
We typically fill this table diagonally or by increasing substring length. As we set entries to True, we can count them. This method avoids re-checking the interior of substrings from scratch by reusing previous results.
Complexity Analysis:
-
Time Complexity: O(n^2). We fill an n \times n DP table by considering all substrings starting and ending at all possible indices, which is essentially O(n^2) work (much better than O(n^3)).
-
Space Complexity: O(n^2) for the DP table . This is the trade-off for using dynamic programming: we use extra space to save time. For n=1000, an n×n table has 1,000,000 entries, which is manageable in modern systems.
Python Code:
Java Code:
Discussion: The DP solution explicitly checks all possible substrings but avoids redundant palindrome checks by referring to smaller substrings (subproblems). Whenever we determine a substring s[i:j] is a palindrome, that knowledge is stored and used when checking larger substrings that wrap around it. This approach is systematic and ensures we count palindromes of all lengths. However, it uses O(n^2) space, which for the given constraints is fine, but for very large strings might be memory-intensive. In this specific problem, the expand-around-center method (Approach 2) achieves the same O(n^2) time without needing extra space, making it a preferred solution. Dynamic programming is still a good practice approach and can be useful in related problems (like finding the longest palindromic substring).
Step-by-Step Walkthrough
Let's summarize how one might tackle counting palindromic substrings step by step:
-
Brute Force Enumeration: Start by considering all possible substrings. For each substring, check if it’s a palindrome by comparing characters or reversing the string. Count all that qualify. This approach will find the correct answer but is inefficient (cubic time complexity).
-
Optimize by Expanding Centers: Instead of checking each substring independently, realize that palindromes are centered. Iterate through each index in the string (and between indices) as a potential center. From each center, expand outwards while the characters match on both sides. Each time you expand successfully, you’ve found a new palindromic substring. This way, you effectively enumerate substrings that are palindromes without checking ones that are not. This brings the complexity down to quadratic.
-
(Alternative) Use Dynamic Programming: Another way to optimize is using a DP table to store results of smaller substrings. You first mark all single letters as palindromes, then check substrings of length 2, 3, and so on. By referring to the results of inner substrings, you avoid rechecking palindromes from scratch. As you fill the table, count every time you set an entry to palindrome. This also runs in O(n^2) time, but uses extra space.
By following these steps (usually opting for step 2 as the best trade-off), you can count all palindromic substrings efficiently.
Common Mistakes and Edge Cases
-
Forgetting Single Characters: Remember that every single character is a palindrome by itself. If you neglect to count those, your result will be off by
nfor a string of lengthn. Both the center-expansion and DP approaches naturally account for single letters (either via the center being the letter itself or the DP base case). -
Even-length Palindromes: A common mistake when expanding around centers is to only consider single-character centers and miss even-length palindromes (which have a "center" between two characters). Always handle the even-length case by initializing two pointers to adjacent indices.
-
Identical Characters: If the string consists of all identical characters (e.g.,
"aaaa"), every substring is palindromic. The number of palindromic substrings will be very large (n*(n+1)/2for length n). Make sure your approach can handle this without unnecessary overchecking. For example, expand-around-center will gracefully count these in O(n^2) time, whereas brute force might be too slow. -
Edge Case – Empty String: Although the problem constraint requires length ≥ 1, it’s good to note that an empty string has 0 palindromic substrings. If you ever generalize the solution, ensure it returns 0 for empty input.
Alternative Variations
-
Longest Palindromic Substring: Instead of counting all palindromic substrings, find the single longest palindrome in the string (and return the substring itself). This is a classic problem that can also be solved by expand-around-center or dynamic programming, and even in O(n) time with Manacher’s algorithm.
-
Count Distinct Palindromic Substrings: Rather than counting all occurrences, count the number of unique palindromic substrings in the string. This is a harder variation because you must avoid double-counting duplicates (it may require advanced data structures like suffix trees/automata or a modified DP).
-
Palindrome Partitioning: Partition the string into as few palindromic substrings as possible (or list all possible palindrome partitionings). This is a different kind of problem that involves recursion or backtracking along with palindrome checks.
Related Problems for Further Practice
-
Longest Palindromic Substring (LeetCode 5): Find the longest palindromic substring in a given string. This problem is closely related and often solved with similar techniques (center expansion or DP).
-
Palindrome Partitioning (LeetCode 131): Given a string, partition it such that every chunk is a palindrome, and return all possible palindrome partitions. It requires generating combinations of palindromic substrings.
-
Shortest Palindrome (LeetCode 214): Find the shortest palindrome you can form from a given string by adding characters to the front. This is a more advanced problem that involves palindrome detection in strings (it can be solved using a combination of string reversal and prefix function/KMP, or Manacher’s algorithm).
GET YOUR FREE
Coding Questions Catalog
