Palindromic Substrings
Problem Statement
Given a string s, return the number of palindromic substrings in it. A substring is contiguous, and two substrings with the same text count separately if they start at different positions.
Input
A string s.
Output
An integer: the total number of palindromic substrings in s.
Constraints
- •
1 <= s.length <= 1000 - •
s consists of lowercase English letters.
Examples
Example 1
s = abc
3Example 2
s = aaa
6Example 3
s = ababa
9Learning Objectives
- Define an interval DP state that answers whether **s[i..j]** is a palindrome.
- Fill substring states by increasing length so the inner interval is already known.
- Count each true interval exactly once, including duplicates at different positions.
- Recognise center expansion as the O(1)-space version of the same palindrome structure.
Intuition
A palindrome is controlled by its outside characters and its inside substring. For a substring s[i..j] to be a palindrome, the endpoints must match. If the substring has length 1 or 2, matching endpoints are enough. For longer substrings, the inside s[i + 1..j - 1] must already be a palindrome.
That naturally creates interval DP. Short substrings answer questions for longer substrings. Once an interval becomes true, increment the count immediately, because the problem counts substrings by position rather than by unique text.
Common mistakes
- ×Counting unique palindrome texts instead of all palindromic positions.
- ×Filling by start index in an order where **dp[i + 1][j - 1]** has not been computed yet.
- ×Forgetting that every one-character substring is a palindrome.
- ×Mishandling even-length palindromes such as **aa**.
- ×Using subsequence logic; this problem is about contiguous substrings only.
State Definition
Let dp[i][j] be true when the substring s[i..j] is a palindrome. The answer is the number of pairs (i, j) for which dp[i][j] is true.
State Transition
For every substring length from 1 to n, evaluate all starts i and ends j = i + length - 1.
A substring is a palindrome when the endpoints match and the inside is valid: s[i] == s[j] and either length <= 2 or dp[i + 1][j - 1] is true. Length 1 is automatically true through this rule because the endpoint is the same character. Length 2 only needs matching endpoints. Each time the condition is true, set dp[i][j] = true and add 1 to the answer.
Solutions
Solution 1: Interval DP by substring length
Fill a boolean table from shorter substrings to longer substrings. The table tells whether each interval is a palindrome, and the answer increments as soon as an interval becomes true.
Step-by-step
- Create a n x n boolean table.
- Iterate length from 1 to n.
- For each start, compute the end of that length.
- If endpoints match and the inside is already palindromic, mark the interval true and increment count.
- Return count after all lengths are processed.
O(n^2)
O(n^2)
There are O(n^2) substrings, and each state is checked in O(1).
Java implementation
Solution 2: Expand around every center
Use this when only the count is needed and you want the same O(n^2) time with O(1) extra space. It is often the cleanest interview implementation after you explain the interval relationship.
Every palindrome has a center: either one character for odd length or a gap between two characters for even length. Expanding from each center counts all palindromes that share that center.
Step-by-step
- For each index, expand once with left = right for odd-length palindromes.
- Expand again with right = left + 1 for even-length palindromes.
- During expansion, each successful matching pair identifies one palindromic substring.
- Sum the counts from all centers and return the total.
O(n^2)
O(1)
Each expansion can grow across the string, and there are O(n) centers.
Java implementation
Dry Run
Sample input
s = aaa. Fill the interval DP table by increasing substring length and count every true interval.
| length | substrings checked | new palindromes | count after length | why |
|---|---|---|---|---|
| 1 | a at 0; a at 1; a at 2 | 3 | 3 | Every one-character substring is a palindrome. |
| 2 | aa at 0..1; aa at 1..2 | 2 | 5 | Both adjacent pairs have matching endpoints. |
| 3 | aaa at 0..2 | 1 | 6 | Endpoints match and the inner substring at 1..1 is true. |
The total is 6: three length-1 palindromes, two length-2 palindromes, and one length-3 palindrome.
Complexity Analysis
The interval DP and center-expansion solutions both take O(n^2) time. Center expansion is preferable when you only need the count; interval DP is useful when later logic needs reusable palindrome states.
Interval DP by substring length
O(n^2)
O(n^2)
There are O(n^2) substrings, and each state is checked in O(1).
Expand around every center
O(n^2)
O(1)
Each expansion can grow across the string, and there are O(n) centers.
Interview Tips
Clarify that duplicate text at different indices counts multiple times. Then present the endpoint-and-inside recurrence and fill by increasing length. If you switch to center expansion, connect it back to the same idea: expanding keeps validating matching endpoints around an already valid center.
Likely follow-ups
- How would you return the longest palindromic substring instead of the count?
- How would you count only palindromes of length at least **k**?
- How would you list all palindromic substrings without duplicates by text?
- What changes if the input can contain uppercase letters and punctuation?
Similar Problems
Key Takeaways
- Palindromic substring DP is an interval DP over **s[i..j]**.
- Shorter intervals must be solved before longer intervals because the transition reads the inside substring.
- The answer counts true positions, not distinct palindrome values.
- Center expansion is the O(1)-space counterpart when the table is not needed later.