Definition
- Boolean DP table where
dp[i][j]is true when the substring from index i to j is a palindrome. - Recurrence is
dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1]), meaning the ends match and the inner range is a palindrome or the range is short enough. - Length-ordered fill processes ranges from shortest to longest so inner results are available.
- Answer tracking keeps the start and length of the longest range marked true.
- O(n squared) time and space for the DP table; expand-around-center gives the same time with O(1) space.
The National Bank of India scans account statement memo fields for the longest unbroken run of characters that reads the same both ways. The fraud team treats long symmetric runs as suspicious auto-generated noise. Unlike the subsequence version, here the characters must sit next to each other with no gaps.
Understanding the Concepts
What is the problem?
Given a string, find the longest contiguous substring that reads the same forward and backward. This is the DP approach to the same problem solved by expand-around-center in Q1447. The DP version explicitly builds a table of which ranges are palindromes.
package com.bank.dsa;
public class LongestPalSubstringDP {
public static String longestPalindrome(String s) {
int n = s.length();
if (n < 2) return s;
boolean[][] dp = new boolean[n][n];
int start = 0, maxLen = 1;
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = true;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
}
Why use DP instead of expand-around-center?
The DP approach builds a reusable palindrome table that other problems can query in O(1). For example, palindromic partitioning needs to know whether arbitrary ranges are palindromes. The expand-around-center approach is better for standalone longest-palindrome queries because it uses O(1) space.
| Approach | Time | Space | Reusable table |
|---|---|---|---|
| DP table | O(n squared) | O(n squared) | Yes |
| Expand-around-center | O(n squared) | O(1) | No |
| Manacher's | O(n) | O(n) | Yes (radii) |
package com.bank.dsa;
public class ComparisonDemo {
public static void main(String[] args) {
String s = "ABCBA";
System.out.println("DP: " + LongestPalSubstringDP.longestPalindrome(s));
System.out.println("Expand: " + LongestPalindromicSubstring.longestPalindrome(s));
}
}
DP: ABCBA
Expand: ABCBA
How does the recurrence work?
- A range [i, j] is a palindrome when:
- The characters at both ends match:
s.charAt(i) == s.charAt(j) - Either the range is short (length 1 or 2) or the inner range [i+1, j-1] is also a palindrome.
package com.bank.dsa;
public class RecurrenceDemo {
public static void main(String[] args) {
String s = "ABCBA";
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = true;
for (int j = i + 1; j < n; j++) {
boolean endsMatch = s.charAt(i) == s.charAt(j);
boolean innerOk = (j - i < 2) || dp[i + 1][j - 1];
dp[i][j] = endsMatch && innerOk;
if (dp[i][j]) {
System.out.println("Palindrome [" + i + "," + j + "]: " + s.substring(i, j + 1));
}
}
}
}
}
Palindrome [0,4]: ABCBA
Palindrome [1,3]: BCB
What is the fill order?
The table must be filled so that the inner range [i+1, j-1] is decided before the outer range [i, j]. This is achieved by iterating i from n-1 down to 0 and j from i+1 up to n-1. Alternatively, iterate by increasing range length.
package com.bank.dsa;
public class FillOrderDemo {
public static void main(String[] args) {
String s = "ABA";
int n = s.length();
boolean[][] dp = new boolean[n][n];
// Fill by decreasing i
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = true;
System.out.println("Base: dp[" + i + "][" + i + "]=true");
for (int j = i + 1; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
System.out.println("dp[" + i + "][" + j + "]=" + dp[i][j]);
}
}
}
}
Base: dp[2][2]=true
dp[2][2]=true
Base: dp[1][1]=true
dp[1][2]=false
Base: dp[0][0]=true
dp[0][1]=false
dp[0][2]=true
What are the edge cases?
An empty string returns empty. A single character returns itself. A string of all identical characters has the entire string as its longest palindrome. A string with no palindrome longer than 1 returns any single character.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(LongestPalSubstringDP.longestPalindrome("")); // ""
System.out.println(LongestPalSubstringDP.longestPalindrome("A")); // "A"
System.out.println(LongestPalSubstringDP.longestPalindrome("AAAA")); // "AAAA"
System.out.println(LongestPalSubstringDP.longestPalindrome("ABCD")); // "A"
}
}
A
AAAA
A
What is the time and space complexity?
Time is O(n squared) because the table has n squared entries and each takes O(1) to compute. Space is O(n squared) for the boolean table. Expand-around-center achieves the same time with O(1) space, making it preferable when the table is not needed by other problems.
How does this differ from the palindromic subsequence DP?
The palindromic substring DP uses a boolean table (is this range a palindrome?) while the palindromic subsequence DP uses an integer table (longest palindromic subsequence of this range). On a mismatch, the substring version sets false (contiguity broken), while the subsequence version takes the max of dropping one end (gaps allowed).
What are common interview follow-up questions?
- How would you count all palindromic substrings using this DP table?
- How would you find the minimum cuts for palindromic partitioning using this table?
- What is the space-optimized version of this DP?
- How does Manacher's algorithm achieve O(n) time?
Visual Overview
String: "ABCBA" (n=5)
DP Table (true entries shown):
j=0 j=1 j=2 j=3 j=4
i=0 [ T ... T ] ← "ABCBA"
i=1 [ T T ] ← "BCB"
i=2 [ T ] ← "C"
i=3 [ T ] ← "B"
i=4 [ T ] ← "A"
Fill order: i from 4 down to 0, j from i+1 up
Recurrence:
dp[i][j] = s[i]==s[j] && (j-i<2 || dp[i+1][j-1])
dp[0][4]: s[0]='A'==s[4]='A' && dp[1][3]=true ── TRUE
Longest palindrome: "ABCBA" (length 5)
Key Takeaway
The Longest Palindromic Substring via DP builds a boolean table where dp[i][j] is true when the substring from i to j is a palindrome. The recurrence is that a range is a palindrome when its two ends match and either the range has length one or two or the strictly inner range is also a palindrome. Rajesh at the National Bank of India uses this to scan memo fields for suspicious symmetric runs.
The table is filled by decreasing i so that inner ranges are decided before outer ranges need them. The answer is the longest range marked true. This runs in O(n squared) time and space. The expand-around-center approach achieves the same time with O(1) space and is preferable for standalone queries.
The DP approach shines when other problems need to query whether arbitrary ranges are palindromes. Palindromic partitioning, for example, reuses this exact table as its foundation. Without it, each query would require a separate O(n) scan. Manacher's algorithm achieves O(n) time by computing palindrome radii with a mirror property, but is rarely needed in interviews.
The key distinction from the palindromic subsequence DP is that a mismatch resets to false (contiguity broken) in the substring version, while the subsequence version carries the better neighbor forward (gaps allowed). Understanding this difference is what shows mastery of both pattern families.
Remember one sentence: a contiguous range is a palindrome when its ends match and the inner range is already a palindrome, filled by increasing length.
---