Palindromic Substrings (DP)
dp[i][j] = true if substring from i to j is a palindrome. Base cases: single chars and two equal adjacent chars. For longer strings: dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1].
How It Works
The palindrome DP table answers 'is the substring from i to j a palindrome?' for every pair. Define dp[i][j] as true when s[i..j] is a palindrome. Base cases: every single character is a palindrome, and two adjacent characters are one when they match. The recurrence is dp[i][j] = (s[i] == s[j]) AND dp[i+1][j−1] — the ends must match and the interior must already be a palindrome.
Because each entry depends on a shorter substring, fill the table by increasing substring length (or iterate i downward and j upward). Construction costs O(n²) time and space, after which every palindrome query is O(1). That constant-time lookup is what makes the table valuable as a preprocessing step for partitioning and counting problems.
Step-by-Step Visualization
Code
static int countPalindromicSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for (int len = 1; len <= n; len++)
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && (len <= 3 || dp[i+1][j-1])) {
dp[i][j] = true;
count++;
}
}
return count;
}Tips & Gotchas
Practice Problems
- 1Palindromic Substrings
- 2Longest Palindromic Substring
- 3Palindrome Partitioning II
- 4Longest Palindromic Subsequence
About the String DP Pattern
When string problems involve comparing two strings character by character (subsequences, transformations, matching), dynamic programming builds the solution from smaller substrings up to the full strings.
Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).
Common String Interview Problems
- Longest Substring Without Repeating Characters
- Valid Anagram
- Longest Palindromic Substring
- Minimum Window Substring
- Group Anagrams
Frequently Asked Questions
Why does the iteration order of the DP table matter?
dp[i][j] reads dp[i+1][j−1], a strictly shorter substring, so that entry must be computed first. Iterating by increasing substring length, or with i descending and j ascending, guarantees the dependency exists before it is read; a naive row-major fill silently reads uninitialized values.
Should I use this table or expand-around-center for counting palindromic substrings?
Both are O(n²) time, but expansion needs only O(1) space, making it the better standalone answer. The DP table earns its O(n²) memory when downstream logic, like partitioning with minimum cuts, must query arbitrary substrings repeatedly.