#647 Palindromic Substrings
the problem
In plain words
Count the substrings of s that read the same forwards and backwards. A substring is a contiguous block of letters, and blocks at different positions count separately even when they spell the same thing.
in s = "abc"
out 3
Only the single letters.
in s = "aaa"
out 6
Three "a", two "aa", one "aaa".
- 1 ≤ s.length ≤ 1000
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternExpand around centerInterval DP
Every palindrome has a centre — a letter or the gap between two letters — and grows outward one letter on each side. Try all 2n − 1 centres and count every step that still matches.
solutions
From brute force to optimal
For each (i, j), test s[i..j] with two pointers.
- Two loops over start and end.
- Two-pointer palindrome check.
- Count the hits.
n(n + 1)/2 substrings × O(n) check — about 8·10⁷ comparisons for 1,000 equal letters.
A few indices.
class Solution { public int countSubstrings(String s) { int count = 0; for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { if (isPalindrome(s, i, j)) count++; // test every substring s[i..j] } } return count; } private boolean isPalindrome(String s, int lo, int hi) { while (lo < hi) { if (s.charAt(lo++) != s.charAt(hi--)) return false; } return true; }}s[i..j] is a palindrome when its ends match and its inside is one (or is shorter than 2).
- i from n − 1 down to 0, j from i up.
- pal[i][j] = s[i] == s[j] && (j − i < 2 || pal[i + 1][j − 1]).
- Count the true cells.
n(n + 1)/2 cells, O(1) each.
The boolean table (1 MB for n = 1000) — worth it when later steps reuse it.
class Solution { public int countSubstrings(String s) { int n = s.length(), count = 0; boolean[][] pal = new boolean[n][n]; // pal[i][j]: is s[i..j] a palindrome? for (int i = n - 1; i >= 0; i--) { // i downward, so row i + 1 is ready for (int j = i; j < n; j++) { // ends match, and the inside is empty, one char, or itself a palindrome pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]); if (pal[i][j]) count++; } } return count; }}2n − 1 centres; each successful expansion step is one more palindrome.
- For each c: count += expand(c, c) + expand(c, c + 1).
- expand grows lo−−, hi++ while the ends match, counting each step.
2n − 1 centres × up to n/2 steps; at most n(n + 1)/2 successful steps in total.
No table.
class Solution { public int countSubstrings(String s) { int count = 0; for (int c = 0; c < s.length(); c++) { count += expand(s, c, c); // odd lengths: centre on a letter count += expand(s, c, c + 1); // even lengths: centre on the gap after it } return count; } /** Counts the palindromes that share one centre: each successful step outward is one more. */ private int expand(String s, int lo, int hi) { int found = 0; while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) { found++; // s[lo..hi] is a palindrome lo--; hi++; } return found; }}Count from every centre
in the room
How to say it in the interview
talk track
- "Every palindrome grows from a centre; there are 2n − 1 centres — n letters and n − 1 gaps."
- "Each successful expansion is a new palindrome, so I count inside the loop."
- Mention the pal[i][j] table as the alternative when later steps need it, and Manacher's O(n) only as a follow-up.
traps
- Forgetting even-length palindromes: "abba" grows from the gap between the two b's.
- Filling pal[i][j] with i going up: pal[i + 1][j − 1] isn't ready yet. Go i downward, or by length.
what they ask next
Follow-ups
O(n) time?
Manacher's algorithm reuses the mirror image inside a palindrome it already knows, so no comparison is repeated; it finds the radius at every centre in O(n). Rarely expected in interviews.
The longest palindromic substring instead (LC 5)?
Same centres; keep the longest instead of counting — it's in the Dynamic Programming chapter.
before you submit
Edge cases to test
- One letter → 1.
- All letters equal → n(n + 1)/2: every substring counts ("aaa" → 6).
- No repeats ("abc") → n: only the single letters.
practise next
Similar problems
- #5Longest Palindromic SubstringMediumin Dynamic Programming
- #131Palindrome PartitioningMediumin Backtracking
- #125Valid PalindromeEasyin Two Pointers