Dynamic Programming · LC #647
Palindromic Substrings
Count total palindromic substrings by expanding around every center (odd + even). Increment a counter on each successful expansion step.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Count the number of palindromic substrings in string `s`.
Sample I/O
Input: s = "abc"
Output: 3 ("a","b","c")
Input: s = "aaa"
Output: 6 ("a","a","a","aa","aa","aaa")Intuition
How to Think About It
Intuition
DP (expand-around-center) works because every palindrome has a unique center, and each expansion step uncovers exactly one new palindromic substring. Counting expansions directly counts palindromes without listing them.
Core Concept
For each center (odd: i,i; even: i,i+1), expand while s[l]==s[r], incrementing count each time. Total centers: 2n-1. Total work: O(n²). Alternative 2D DP: dp[i][j]=True if palindrome, count Trues.
When to use
Counting all palindromic substrings; often a building block for palindrome partitioning DP.
When NOT to use
When you need distinct palindromic substrings by value (not count of occurrences) - use suffix automaton or Eertree for O(n).
Key Insights
What to Know Cold
- Each successful while-loop iteration in expand() corresponds to exactly one palindromic substring.
- The count includes all single characters (n of them) since every character is trivially a palindrome.
- Reuse the same expand helper as LC 5 - swap "track max" with "increment counter".
- "aaa" has 6: three singles + two length-2 overlapping + one length-3; expand-around-center finds all naturally.
- 2D DP table is equivalent but uses O(n²) space and is harder to code correctly under interview pressure.
1 example
Worked Examples
Count palindromes in "aaa"
s="aaa"; expected 6 palindromic substrings.
Expand around each center, count each valid expansion.
Output: 6
Direct companion to LC 5. Mastering both shows understanding of the expand-around-center template and how minor changes in the accumulation logic yield entirely different results.