Longest Palindromic Subsequence: interval DP

• Interval DP – dp[i][j] stores the longest palindromic subsequence length within the substring from index i to index j.
• Match case – when s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2, the matching ends wrap the inner result.
• Mismatch case – when s[i] != s[j], dp[i][j] = max(dp[i+1][j], dp[i][j-1]), drop whichever end helps less.
• Base case – every single character is a palindrome of length 1, so dp[i][i] = 1.
• Equivalence – the answer equals the LCS of the string with its reverse.

What is the Longest Palindromic Subsequence?

A palindromic subsequence is a sequence of characters from the string that reads the same forwards and backwards, but the characters need not be contiguous. The longest palindromic subsequence (LPS) is the one with the maximum length.

For example, in the string "ABRACADABRA", one palindromic subsequence is "ABAABA" (length 6). Characters are picked from various positions but maintain their relative order.

In banking, the National Bank of India uses reference codes on transactions, and a compliance system flags codes with long palindromic patterns as potential markers for suspicious activity.

How does the interval DP work?

Define dp[i][j] as the length of the longest palindromic subsequence in the substring from index i to index j inclusive. Fill the table by increasing interval length so that smaller intervals are always ready before larger ones.

• Base case: dp[i][i] = 1 because a single character is a palindrome of length 1.
• If s.charAt(i) == s.charAt(j), the two ends match and wrap the inner palindrome: dp[i][j] = dp[i+1][j-1] + 2.
• If s.charAt(i) != s.charAt(j), drop one end: dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]).

The answer is dp[0][n-1], covering the entire string.

package com.bank.service;

public class PalindromePatternDetector {

    public static int longestPalindromicSubsequence(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 interval length
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (code.charAt(i) == code.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        String refCode = "NBIABCBA";
        System.out.println("LPS length: " + longestPalindromicSubsequence(refCode));
    }
}

LPS length: 5

How is this different from Longest Palindromic Substring?

| Aspect | Palindromic Subsequence | Palindromic Substring |
|---|---|---|
| Contiguity | Characters may be non-contiguous | Characters must be contiguous |
| Approach | Interval DP or LCS with reverse | Center expansion or Manacher's algorithm |
| Time | O(n^2) | O(n^2) center expansion, O(n) Manacher's |
| Difficulty | Harder because skipping is allowed | Easier with center expansion |

The substring version can use center expansion because contiguous characters form a window that expands outward. The subsequence version cannot, because non-contiguous characters require the full interval DP.

// Longest Palindromic SUBSTRING via center expansion (contrast)
public static String longestPalindromeSubstring(String s) {
    int start = 0, maxLen = 1;
    for (int center = 0; center < s.length(); center++) {
        // Odd length
        int lo = center, hi = center;
        while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
            if (hi - lo + 1 > maxLen) { start = lo; maxLen = hi - lo + 1; }
            lo--; hi++;
        }
        // Even length
        lo = center; hi = center + 1;
        while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
            if (hi - lo + 1 > maxLen) { start = lo; maxLen = hi - lo + 1; }
            lo--; hi++;
        }
    }
    return s.substring(start, start + maxLen);
}

Why is this equivalent to LCS of the string with its reverse?

The longest palindromic subsequence of a string S is exactly the longest common subsequence (LCS) of S and its reverse. A subsequence that reads the same forwards and backwards must appear in both S and reverse(S), and the longest such common subsequence is by definition the longest palindromic subsequence.

This gives an alternative implementation using the standard LCS algorithm.

public static int lpsViaLCS(String code) {
    String reversed = new StringBuilder(code).reverse().toString();
    int n = code.length();
    int[][] dp = new int[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (code.charAt(i - 1) == reversed.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][n];
}

What is the fill order and why does it matter?

The cell dp[i][j] depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1]. All three are from smaller intervals. To ensure they are ready, either iterate i from the end backward and j forward, or iterate by increasing interval length.

Iterating by length is the clearest approach: length 1 (base cases), then length 2, then length 3, up to length n.

// Fill order: increasing interval length
for (int len = 2; len <= n; len++) {       // length of window
    for (int i = 0; i <= n - len; i++) {   // left end
        int j = i + len - 1;               // right end
        // dp[i][j] uses dp[i+1][j-1], dp[i+1][j], dp[i][j-1]
        // all have length < len, so already computed
    }
}

What are the edge cases?

• Empty string – return 0.
• Single character – return 1, it is its own palindrome.
• All same characters – the entire string is a palindrome, return n.
• No repeated characters – every character stands alone, return 1.
• Already a palindrome – the LPS length equals the string length.

// Edge case: all same characters
String allSame = "AAAA";
// dp fills: every pair matches, dp[0][3] = 4
System.out.println(longestPalindromicSubsequence(allSame)); // 4

What is the time and space complexity?

Time is O(n^2) because the table has n^2 cells and each takes O(1) to fill. Space is O(n^2) for the table. Space can be reduced to O(n) by observing that each row depends only on the next row, but the implementation is trickier.

For banking reference codes of typical length (10-20 characters), this is instantaneous. For very long strings (thousands of characters), the quadratic space might matter, and the rolling-row optimisation becomes relevant.

What are common mistakes?

The most common mistake is confusing subsequence with substring and using center expansion, which only finds contiguous palindromes.

// WRONG: using center expansion for subsequence
// Center expansion finds "BCB" in "ABCBA" but misses "ABCBA" if chars are non-contiguous
// It cannot handle skipping characters

// CORRECT: use interval DP for subsequence
// dp[i][j] properly considers skipping characters by dropping one end

Another mistake is the fill order. If you iterate i forward and j forward, dp[i+1][j-1] might not be computed yet.

What should a senior engineer know?

A senior engineer should know the LCS equivalence, because it connects two seemingly different problems and shows that palindromic subsequence is just a special case of the general LCS framework. They should also know that recovering the actual subsequence (not just its length) requires backtracking through the DP table, following the choices that led to each cell's value.