Definition
- Range DP – dp[i][j] is the length of the longest palindromic subsequence in the substring from index i to index j.
- Match case – when s[i] == s[j], those two characters wrap a palindrome: dp[i][j] = 2 + dp[i+1][j-1].
- Mismatch case – when s[i] != s[j], at least one end is not in the outer pair: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
- Base case – a single character is a palindrome of length 1: dp[i][i] = 1.
- Fill order – fill by increasing range length so inner ranges are ready before outer ranges.
The National Bank of India stores a reference code on each transaction and measures the longest symmetric core inside it. A symmetric core reads the same forward and backward when you are allowed to skip characters. The bank uses this as a lightweight integrity marker.
Understanding the Concepts
What is the Longest Palindromic Subsequence?
Given a string, find the length of its longest subsequence that reads the same forward and backward. A subsequence keeps relative order but characters need not be contiguous. For example, in "bbbab" the longest palindromic subsequence is "bbbb" with length 4.
package com.bank.integrity;
public class LongestPalindromicSubseq {
public static int longestPalSubseq(String code) {
int n = code.length();
int[][] dp = new int[n][n];
// Base case: single characters
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// Fill by increasing range length
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (code.charAt(i) == code.charAt(j)) {
dp[i][j] = 2 + dp[i + 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}
Why does the two-ended recurrence work?
You reason about a range by examining its two ends. If the character at the left end equals the character at the right end, those two characters form the outer layer of a palindrome, so the answer is 2 plus the best palindrome in the inner range (without those two characters). If the ends differ, at least one cannot be part of an outer pair, so you drop one end and take the larger result from the two shorter ranges.
// Match: s[i] == s[j]
// dp[i][j] = 2 + dp[i+1][j-1]
// Example: s="aba", i=0('a'), j=2('a')
// Both 'a' chars wrap inner "b" → 2 + dp[1][1] = 2 + 1 = 3
// Mismatch: s[i] != s[j]
// dp[i][j] = max(dp[i+1][j], dp[i][j-1])
// Example: s="abc", i=0('a'), j=2('c')
// Drop 'a': dp[1][2] or drop 'c': dp[0][1]
// Both are 1, so dp[0][2] = 1
How does the DP table fill step by step?
For the string "bbbab", the table fills by increasing range length. The diagonal holds 1s (single characters), then ranges of length 2, then 3, and so on.
package com.bank.integrity;
public class DPTrace {
public static void trace() {
String code = "bbbab";
// Diagonal (length 1): dp[i][i] = 1 for all i
// Length 2:
// dp[0][1]: 'b'=='b' → 2+dp[1][0]=2+0=2
// dp[1][2]: 'b'=='b' → 2+dp[2][1]=2+0=2
// dp[2][3]: 'b'!='a' → max(dp[3][3],dp[2][2])=max(1,1)=1
// dp[3][4]: 'a'!='b' → max(dp[4][4],dp[3][3])=max(1,1)=1
// Length 3:
// dp[0][2]: 'b'=='b' → 2+dp[1][1]=2+1=3
// dp[1][3]: 'b'!='a' → max(dp[2][3],dp[1][2])=max(1,2)=2
// dp[2][4]: 'b'=='b' → 2+dp[3][3]=2+1=3? Wait 'b'!='b'? s[2]='b',s[4]='b' → match!
// 2+dp[3][3]=2+1=3
// Length 4:
// dp[0][3]: 'b'!='a' → max(dp[1][3],dp[0][2])=max(2,3)=3
// dp[1][4]: 'b'=='b' → 2+dp[2][3]=2+1=3
// Length 5:
// dp[0][4]: 'b'=='b' → 2+dp[1][3]=2+2=4
// Answer: dp[0][4] = 4 (subsequence "bbbb")
System.out.println("LPS length: " +
LongestPalindromicSubseq.longestPalSubseq(code));
}
}
LPS length: 4
How is this different from longest palindromic substring?
The substring version requires characters to be contiguous. The subsequence version allows gaps. For "bbbab", the longest palindromic substring is "bbb" (length 3, contiguous), but the longest palindromic subsequence is "bbbb" (length 4, skipping 'a'). The substring version uses a different DP where dp[i][j] is a boolean indicating whether s[i..j] is a palindrome.
// Subsequence: allows gaps, dp[i][j] = length
// "bbbab" → "bbbb" (length 4, skips 'a')
// Substring: contiguous, dp[i][j] = boolean
// "bbbab" → "bbb" (length 3)
// Subsequence recurrence: dp[i][j] = 2 + dp[i+1][j-1] if match
// Substring recurrence: dp[i][j] = true if s[i]==s[j] && dp[i+1][j-1]
How do you recover the actual subsequence?
To recover the actual palindromic subsequence, walk the DP table from dp[0][n-1] backward. If s[i] == s[j], add both characters and move inward. If not, move toward the larger of dp[i+1][j] and dp[i][j-1].
package com.bank.integrity;
public class RecoverSubsequence {
public static String recoverLPS(String code) {
int n = code.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int i = n - 2; i >= 0; i--)
for (int j = i + 1; j < n; j++)
dp[i][j] = code.charAt(i) == code.charAt(j)
? 2 + dp[i + 1][j - 1]
: Math.max(dp[i + 1][j], dp[i][j - 1]);
// Walk the table
StringBuilder front = new StringBuilder();
StringBuilder back = new StringBuilder();
int i = 0, j = n - 1;
while (i < j) {
if (code.charAt(i) == code.charAt(j)) {
front.append(code.charAt(i));
back.insert(0, code.charAt(j));
i++; j--;
} else if (dp[i + 1][j] > dp[i][j - 1]) {
i++;
} else {
j--;
}
}
if (i == j) front.append(code.charAt(i)); // middle character
return front.toString() + back.toString();
}
public static void main(String[] args) {
System.out.println(recoverLPS("bbbab")); // "bbbb"
}
}
bbbb
What is the time and space complexity?
| Aspect | Complexity | Notes |
|---|---|---|
| Time | O(n^2) | Fill n*n table |
| Space | O(n^2) | 2D DP table |
| Space-optimized | O(n) | Only two rows needed at a time |
What are edge cases?
Edge cases include a single character (answer is 1), an already-palindromic string (answer is the string length), and a string with no repeating characters (answer is 1).
package com.bank.integrity;
public class EdgeCases {
public static void test() {
System.out.println(LongestPalindromicSubseq.longestPalSubseq("a")); // 1
System.out.println(LongestPalindromicSubseq.longestPalSubseq("abcba")); // 5
System.out.println(LongestPalindromicSubseq.longestPalSubseq("abcdef")); // 1
}
}
1
5
1
What should a senior engineer know?
A senior engineer should mention the LCS connection: the longest palindromic subsequence of a string equals the longest common subsequence of the string and its reverse. This alternative approach also runs in O(n^2) but may be easier to code if you already have an LCS implementation.
// LCS connection:
// LPS(s) = LCS(s, reverse(s))
// Example: s="bbbab", reverse="babbb"
// LCS("bbbab", "babbb") = "bbbb" (length 4)
Visual Overview
DP Table for "bbbab"
=====================
b b b a b
b [ 1 2 3 3 4 ]
b [ 1 2 2 3 ]
b [ 1 1 3 ]
a [ 1 1 ]
b [ 1 ]
Answer: dp[0][4] = 4
Recurrence Logic
=================
Range [i, j]:
┌─────────────────────────────┐
│ s[i] == s[j]? │
├──────────┬──────────────────┤
│ Yes │ No │
│ │ │
│ 2 + dp │ max(dp[i+1][j], │
│ [i+1] │ dp[i][j-1]) │
│ [j-1] │ │
└──────────┴──────────────────┘
Example: s="bbbab", [0,4]
s[0]='b' == s[4]='b' → 2 + dp[1][3] = 2 + 2 = 4
Fill Order
==========
Fill diagonals of increasing length:
Length 1: dp[0][0], dp[1][1], ..., dp[4][4] (all = 1)
Length 2: dp[0][1], dp[1][2], dp[2][3], dp[3][4]
Length 3: dp[0][2], dp[1][3], dp[2][4]
Length 4: dp[0][3], dp[1][4]
Length 5: dp[0][4] ← answer
Key Takeaway
The Longest Palindromic Subsequence is the canonical Palindromic Subsequence DP problem, and the key insight is reasoning about a range by its two ends. If the characters at the left and right ends match, they form the outer layer of a palindrome, so the answer is 2 plus the longest palindromic subsequence of the inner range. If they differ, at least one end cannot be part of an outer pair, so you drop one end and take the larger of the two shorter ranges.
You build the table bottom-up, seeding the diagonal with 1 (every single character is a palindrome), then filling ranges of increasing length so that every inner range is ready before the outer range that depends on it. The answer sits in dp[0][n-1], the full range. The time and space are both O(n^2).
At the National Bank of India, Rajesh used this to measure the longest symmetric core inside each transaction reference code, because the bank used symmetric cores as lightweight integrity markers. The two-ended range DP over each code returned the length of the longest palindromic subsequence.
The senior-level insight is the LCS connection: the longest palindromic subsequence of a string equals the longest common subsequence of the string and its reverse. This alternative approach is equivalent in complexity but may be easier to implement when an LCS function is already available. Always clarify that the subsequence version allows gaps, which distinguishes it from the contiguous substring version.
Remember one sentence: match the ends and add 2 to the inner answer, or drop one end and take the larger, filling by increasing range length.
---