Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count how many contiguous substrings are palindromes (each character is a palindrome of length 1, and longer ones add on). The clean answer reuses Longest Palindromic Substring's engine: expand around each of the 2n−1 centers and add 1 to the count for every successful expansion — O(n²) time, O(1) space. A DP table over dp[i][j] is the same complexity but uses O(n²) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize this as Longest Palindromic Substring's twin and reuse center expansion — and whether you correctly count every palindrome, including the n trivial single characters.
Where candidates slip
Counting only once per center instead of once per successful expansion, or forgetting even-length centers so 'aaa' undercounts.
How to stand out
Note out loud that this is the same engine as LC 5, increment inside the expansion loop, and offer the DP table as the alternative while explaining why expansion wins on space.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount palindromic substringsDistinct strings only?YesNo, count allExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Expand Around Center — Count (Optimal)
1Hint 1Explore hintHide hint
You already know how to find the longest palindrome by growing from a center. What changes if you want the COUNT instead of the longest?
2Hint 2Explore hintHide hint
Each time an expansion from a center succeeds (characters match in bounds), you've discovered exactly one more palindrome. Increment then.
3Hint 3Explore hintHide hint
Loop every index, expand both the odd center (i, i) and the even center (i, i+1), and add 1 per successful step of each expansion.
A · Core idea
Walk every index. From each, expand two pointers outward for the odd center (i, i) and again for the even center (i, i+1), incrementing a global counter on each successful match. Sum across all centers.
The reframing from LC 5. Longest Palindromic Substring asks how far each center reaches and keeps the maximum. This problem asks how many palindromes exist — and here's the key observation: a center that expands k times has discovered exactly k palindromes (the length-1 core, then length-3, length-5, … for odd; length-2, length-4, … for even). So instead of comparing lengths after the loop, you count++ inside the loop, once per successful expansion step. Same traversal, different accumulator.
Why the increment is inside the loop, not after. A common bug is to expand fully and then add 1 — that counts each center as a single palindrome and throws away all the nested ones. The whole point is that every concentric layer is its own palindrome: in 'aaa', the center at index 1 expands twice ('a' → 'aaa'), contributing 2, not 1. Putting count++ as the first statement of each successful iteration captures every layer.
Why both center types, every index. Odd centers (i, i) catch 'a', 'aba', 'ababa'; even centers (i, i+1) catch 'aa', 'abba'. Run both at each index and you've covered all 2n − 1 centers. Skipping even centers undercounts any string with repeated adjacent characters — exactly the worst case the problem is built around.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "aaa"Array state
l=1, r=1
'a' matches itself → count += 1
6C · Code with teaching comments
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
A center expanding k times = k palindromes, because each concentric ring is itself a palindrome. That's why counting is just 'increment per successful expansion' — you're tallying rings, not centers. Recognizing that nesting structure is what turns the longest-palindrome engine into a counter for free.
ComplexityO(n²) time, O(1) space — 2n−1 centers, each expanding at most O(n) steps with O(1) work per step → O(n²) time. Only an integer counter is stored → O(1) space.
E · Edge cases and pitfalls5s = "abc" — Every odd center adds 1, every even center adds 0 (no adjacent matches). Total = 3 single characters.Explore edge casesHide edge cases
Edge cases handled
s = "abc"Every odd center adds 1, every even center adds 0 (no adjacent matches). Total = 3 single characters.s = "a"Single odd center (0,0) adds 1; even center (0,1) is out of bounds and adds 0. Returns 1.
Pitfalls
- Adding 1 after the expansion instead of once per step — counts each center as a single palindrome.
- Skipping the even center (i, i+1) — undercounts every repeated-adjacent run.
- Using a too-small integer type for huge inputs — though n=1000 maxes at ~500k, fine for int.
Approach 2 of 2
DP Table over dp[i][j]
1Hint 1Explore hintHide hint
Define dp[i][j] = is the substring s[i..j] a palindrome? How does a longer palindrome relate to a shorter one inside it?
2Hint 2Explore hintHide hint
s[i..j] is a palindrome iff its ends match (s[i]==s[j]) AND its interior s[i+1..j-1] is already known to be a palindrome.
3Hint 3Explore hintHide hint
Fill the table by increasing substring length (or iterate i downward, j upward) so dp[i+1][j-1] is computed before dp[i][j]. Count every true cell.
A · Core idea
Let dp[i][j] be true when s[i..j] is a palindrome. A substring is a palindrome exactly when its two ends match and the strictly-inner substring is also a palindrome. Count every cell that turns out true.
The recurrence and its base cases. dp[i][j] = (s[i] == s[j]) && (j − i < 2 || dp[i+1][j-1]). The j − i < 2 guard covers the two base cases with no inner substring: length 1 (i == j) is always a palindrome, and length 2 (j == i+1) is a palindrome iff the two characters match. For length ≥ 3 the answer leans on the smaller, already-solved dp[i+1][j-1].
Why fill order matters. dp[i][j] depends on dp[i+1][j-1] — a shorter substring sitting one step inside. If you fill in the wrong order you'll read a cell that hasn't been computed yet and get garbage. Two correct orders: iterate by increasing substring length, or run the outer loop i from n−1 down to 0 and the inner j from i up to n−1. Either guarantees the inner cell is ready.
Why we still prefer expansion in an interview. This table is conceptually clean and a great way to show you understand palindromic DP, but it pays O(n²) memory for the same O(n²) time as center expansion, and the fill-order trap is an easy place to slip. State it as the DP formulation, then point out that expand-around-center gets the identical complexity in O(1) space.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "aba"Array state
length 1
diagonal cells true: each single char is a palindrome
4C · Code with teaching comments
Reference implementation previewpublic int countSubstrings(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int count = 0; for (int i = n - 1; i >= 0; i--) {Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
The table makes the nesting explicit: a palindrome is two matching ends wrapped around a smaller palindrome. That's literally the same concentric-ring idea center expansion exploits — the table just memoizes it instead of recomputing on the fly.
ComplexityO(n²) time, O(n²) space — Filling an n×n table with O(1) work per cell is O(n²) time; the table itself is O(n²) space.
E · Edge cases and pitfalls4s = "aa" — dp[0][0], dp[1][1] true (singles), dp[0][1] true via j-i<2 base case → count = 3.Explore edge casesHide edge cases
Edge cases handled
s = "aa"dp[0][0], dp[1][1] true (singles), dp[0][1] true via j-i<2 base case → count = 3.
Pitfalls
- Filling i ascending without the right inner dependency — reads dp[i+1][j-1] before it's set.
- Forgetting the j - i < 2 guard so length-2 palindromes try to read a non-existent inner cell.
- Allocating O(n²) booleans when O(1)-space center expansion would do — wasteful for large n.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int countSubstrings(String s) { int count = 0; for (int i = 0; i < s.length(); i++) { count += expand(s, i, i); count += expand(s, i, i + 1);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting once per center, not per layer
A center that expands k times contains k palindromes. Adding 1 after the loop ignores the nested ones, so 'aaa' returns far less than 6.
Explore the code comparisonHide the code comparison
Counting once per center, not per layer
A center that expands k times contains k palindromes. Adding 1 after the loop ignores the nested ones, so 'aaa' returns far less than 6.
Don't write this
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
return 1 # only the center countedWrite this instead
def expand(l, r):
found = 0
while l >= 0 and r < n and s[l] == s[r]:
found += 1
l -= 1
r += 1
return found2Skipping even-length centers
Only expanding (i, i) misses 'aa', 'abba', etc. For repeated-character strings — the worst case — the count is badly low.
Explore the code comparisonHide the code comparison
Skipping even-length centers
Only expanding (i, i) misses 'aa', 'abba', etc. For repeated-character strings — the worst case — the count is badly low.
Don't write this
for (int i = 0; i < n; i++) {
count += expand(s, i, i); // odd only
}Write this instead
for (int i = 0; i < n; i++) {
count += expand(s, i, i);
count += expand(s, i, i + 1);
}3Wrong DP fill order
dp[i][j] needs dp[i+1][j-1]. Iterating i from 0 upward reads that inner cell before it's set, producing wrong counts.
Explore the code comparisonHide the code comparison
Wrong DP fill order
dp[i][j] needs dp[i+1][j-1]. Iterating i from 0 upward reads that inner cell before it's set, producing wrong counts.
Don't write this
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) { /* dp[i+1][j-1] not ready */ }
}Write this instead
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) { /* dp[i+1][j-1] already filled */ }
}Revise
Carry the pattern into the interview
Pattern to remember
Expand around center — count, don't measure
Code pattern to memorize
count = 0
for center in range(2n - 1):
l, r = center // 2, center // 2 + center % 2
while l >= 0 and r < n and s[l] == s[r]:
count += 1; l -= 1; r += 1Rules to remember
- 1Every successful expansion is one more palindrome —
count++inside the while loop, not after it. - 2Run both center types per index:
(i, i)for odd lengths and(i, i+1)for even lengths — 2n − 1 centers total. - 3Single characters always count: the loop fires at least once for every
(i, i)center. - 4The DP recurrence is
dp[i][j] = s[i]==s[j] && (j−i < 2 || dp[i+1][j−1]); fill by increasing substring length or you'll read unfilled cells. - 5Prefer center-expansion in interviews — same O(n²) time but O(1) space and far less index bookkeeping than the table.
Use this pattern when
- Count (rather than find) substrings with a symmetric, center-growable property
- n is modest (≤ ~1000) so O(n²) is fine
- You already know expand-around-center from Longest Palindromic Substring
- Need both odd and even palindromes tallied in one pass per index
Choose another pattern when
- Distinct palindromic substrings only → needs hashing or Eertree, not raw counting
- Palindromic subsequences → interval DP, different recurrence
- Longest one, not the count → track (start, len) instead of incrementing
- n is huge with tight limits → Manacher's gives O(n)
Interview takeaway
Counting palindromic substrings is the same center-expansion trick as finding the longest — you just increment a counter on every successful step instead of comparing lengths. One engine, two problems: see the center and you've solved both.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCenter-Expansion for Palindromes (counting variant). The increment-per-expansion idea reuses Longest Palindromic Substring's engine. When a symmetric property nests in concentric layers, count the layers, not the centers.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Longest Palindromic SubstringSame center expansion, but track the longest (start, len) instead of counting.
- Longest Palindromic SubsequenceSubsequence not substring — interval DP, dp[i][j] = longest palindromic subsequence in s[i..j].
- Palindrome PartitioningComing soonReuse a precomputed isPalindrome DP table to prune the backtracking that cuts the string.
- Remove Palindromic SubsequencesComing soonTrick question — a binary string needs at most 2 removals; reason about palindromes directly.