The O(n) Club: Longest Palindromic Subsequence: Where Dynamic Programming Eats Exponential Time For Breakfast

The O(n) Club: Longest Palindromic Subsequence — Where Dynamic Programming Eats Exponential Time For Breakfast

⚡ TL;DR

Given a string, what’s the length of its longest palindromic subsequence? (Subsequence means: skipping allowed. Palindrome means: reads the same both ways.) Brute force checks every possible subsequence (enjoy your O(2ⁿ) time… not!). Dynamic Programming saves your sanity—just memoize repeated subproblems like a responsible adult:

🧠 How Devs Usually Mess This Up

Raise your hand if you confused substring with subsequence. (Put your hand down, we all do it.) Substrings want everyone together—subsequences are the chill group project where you can skip meetings. Brute-forcing every subsequence is like reading every book at once: possible in theory, disastrous in practice. And don’t even get me started on forgetting those single-letter “palindromes”—that’s the DP diagonal, my friend. Also: No, you won’t always find just one longest palindromic subsequence. There’s often a whole committee of them.

🔍 What’s Actually Going On

Imagine sandwich bookends: If the letters at i and j match, your palindrome grows outward like a CPU in hyperthreading mode. If they don’t, someone’s got to go—try both options. Use a 2D DP table where dp[i][j] means “How long’s the biggest palindrome between i and j?” Fill the table bottom-up, length by length—think building a lasagna, but with more curly braces and less cheese.

🛠️ PseudoCode

Result: The answer’s at dp[0][n-1], classic DP fashion.

return dp[0][n-1];

DP State: If ends match, extend; otherwise, take max left/right shrink.

if (s.charAt(i) == s.charAt(j))
    dp[i][j] = (len == 2) ? 2 : dp[i+1][j-1] + 2;
else
    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);

Expand for Length > 1: For substring lengths 2 up to n:

for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        // ... fill dp[i][j]
    }
}

Initialize: For every character, it’s a length-1 palindrome. Set dp[i][i] = 1 for all i.

for (int i = 0; i < n; i++) dp[i][i] = 1;

💻 The Code

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = (len == 2) ? 2 : 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];
}

⚠️ Pitfalls, Traps & Runtime Smacks

Subsequence ≠ substring. Palindromic subsequence can leapfrog characters; substring’s clingy.
Missed single-char palindromes? That’s how you get weird bugs. Remember: the diagonal.
Multiple answers? Yup. The length is what matters.
2D DP means O(n²) time and space. Acceptable for normal mortals. Space saver tricks? Only if you don’t need the actual sequence, just the length.
That reverse string trick (LCS between s and reversed s)? For bonus brain flex, not routine interviews.