Coding Interview PatternsPalindromic Substrings
MediumDynamic Programming
Palindromic Substrings
Explanation & Solution
Description
Given a string s, return the number of palindromic substrings in it.
A substring is a contiguous sequence of characters within the string. A string is palindromic if it reads the same backward as forward.
Input: s = "abc"
Output: 3
Explanation: The three palindromic substrings are: "a", "b", "c".
Constraints
1 <= s.length <= 1000sconsists of only lowercase English letters.
Approach
Dynamic Programming pattern
1. Initialize a Counter
- Set
count = 0to track the total number of palindromic substrings.
2. Define the Expand Around Center Helper
- Create a function
expandAroundCenter(left, right)that expands outward as long ass[left] === s[right]. - Each successful expansion represents a new palindromic substring, so increment
count.
3. Iterate Through Each Center
- For each index
ifrom0tos.length - 1: - Call
expandAroundCenter(i, i)to count all odd-length palindromes centered ati. - Call
expandAroundCenter(i, i + 1)to count all even-length palindromes centered betweeniandi + 1.
4. Return the Count
- After processing all centers, return
countas the total number of palindromic substrings.
Key Insight
- Every palindrome has a center. By expanding around each possible center (n single-character centers and n-1 double-character centers), we efficiently enumerate all palindromic substrings without needing a DP table.
Time
O(n^2)for each of the n centers, expansion takes up to O(n) time.Space
O(1)only a counter and index variables are used.Visualization
Input:
[a, b, c]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps