Longest Palindromic Subsequence - The Three Approaches

Problem: Given a string s, find the length of the longest palindromic subsequence in it.

Example: s = "bbbab" → 4 (subsequence: "bbbb")

Example: s = "cbbd" → 2 (subsequence: "bb")

Understanding the Problem

A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Key Difference:

Substring: Must be contiguous (e.g., "abc" in "xabcy")
Subsequence: Can skip characters (e.g., "ace" in "abcde")

Palindromic subsequence: A subsequence that reads the same forwards and backwards.

Examples:

"bbbab" → Longest palindromic subsequence is "bbbb" (length 4)
- We skip the 'a' to form "bbbb"
"cbbd" → Longest palindromic subsequence is "bb" (length 2)

1. Pure Recursion (Unoptimized - O(2^n))

The Intuition

Key Insight: For any range [i, j]:

If characters at both ends match (s[i] == s[j]), they can both be included in the palindrome
If they don't match, we have to skip one end and try both options

Recursive Logic:

longestPalindromeSubseq(i, j):
    if i > j: return 0           // empty range
    if i == j: return 1           // single character

    if s[i] == s[j]:
        return 2 + longestPalindromeSubseq(i+1, j-1)  // include both ends
    else:
        return max(
            longestPalindromeSubseq(i+1, j),    // skip left
            longestPalindromeSubseq(i, j-1)     // skip right
        )

public int longestPalindromeSubseq(String s) {
    return helper(s, 0, s.length() - 1);
}

private int helper(String s, int i, int j) {
    // Base cases
    if (i > j) return 0;      // Empty range
    if (i == j) return 1;      // Single character is a palindrome

    // If characters match, include both in palindrome
    if (s.charAt(i) == s.charAt(j)) {
        return 2 + helper(s, i + 1, j - 1);
    }

    // If they don't match, try skipping either end
    int skipLeft = helper(s, i + 1, j);
    int skipRight = helper(s, i, j - 1);

    return Math.max(skipLeft, skipRight);
}

What Happens with `s = "bbbab"`:

helper(0, 4): "bbbab"
  s[0] == s[4]? 'b' == 'b' ✓
  → 2 + helper(1, 3): "bba"
      s[1] == s[3]? 'b' == 'a' ✗
      → max(helper(2, 3), helper(1, 2))
          helper(2, 3): "ba"
            s[2] == s[3]? 'b' == 'a' ✗
            → max(helper(3, 3), helper(2, 2))
                helper(3, 3): "a" → 1
                helper(2, 2): "b" → 1
            → max(1, 1) = 1
          helper(1, 2): "bb"
            s[1] == s[2]? 'b' == 'b' ✓
            → 2 + helper(2, 1) → 2 + 0 = 2
      → max(1, 2) = 2
  → 2 + 2 = 4 ✓

Result: 4 (subsequence "bbbb")

Call Tree Visualization:

helper(0,4) "bbbab"
├── helper(1,3) "bba"
│   ├── helper(2,3) "ba" ✓ COMPUTED
│   │   ├── helper(3,3) → 1
│   │   └── helper(2,2) → 1
│   └── helper(1,2) "bb" ✓ COMPUTED
│       └── helper(2,1) → 0
└── Result: 2 + 2 = 4

Problem: helper(2,3) and helper(1,2) might be computed multiple times
in larger strings!

Why is it Slow?

Overlapping subproblems: Many ranges like [2,3], [1,2] are computed multiple times.

For a string of length n, there are O(n²) unique subproblems, but pure recursion may compute them exponentially many times.

Complexity:

Time: O(2^n) - exponential (each position: skip left or skip right)
Space: O(n) - recursion stack depth

2. Top-Down DP (Memoization - O(n²))

The Intuition

Key Insight: Same recursive logic, but cache results to avoid recomputation.

For each range [i, j], we compute the answer once and store it in memo[i][j].

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    Integer[][] memo = new Integer[n][n];
    return helper(s, 0, n - 1, memo);
}

private int helper(String s, int i, int j, Integer[][] memo) {
    // Base cases
    if (i > j) return 0;
    if (i == j) return 1;

    // Check cache
    if (memo[i][j] != null) {
        return memo[i][j];
    }

    // Calculate result
    int result;
    if (s.charAt(i) == s.charAt(j)) {
        result = 2 + helper(s, i + 1, j - 1, memo);
    } else {
        int skipLeft = helper(s, i + 1, j, memo);
        int skipRight = helper(s, i, j - 1, memo);
        result = Math.max(skipLeft, skipRight);
    }

    // Store in cache
    memo[i][j] = result;
    return result;
}

What Happens with `s = "bbbab"`:

Call helper(0, 4):
  memo[0][4] is null, calculate:
  s[0] == s[4]? 'b' == 'b' ✓
  → 2 + helper(1, 3)
      memo[1][3] is null, calculate:
      s[1] == s[3]? 'b' == 'a' ✗
      → max(helper(2, 3), helper(1, 2))
          helper(2, 3):
            memo[2][3] is null, calculate:
            s[2] == s[3]? 'b' == 'a' ✗
            → max(helper(3, 3), helper(2, 2))
                helper(3, 3): base case → 1
                helper(2, 2): base case → 1
            → max(1, 1) = 1
            → memo[2][3] = 1 ✓
          helper(1, 2):
            memo[1][2] is null, calculate:
            s[1] == s[2]? 'b' == 'b' ✓
            → 2 + helper(2, 1) → 2 + 0 = 2
            → memo[1][2] = 2 ✓
      → max(1, 2) = 2
      → memo[1][3] = 2 ✓
  → 2 + 2 = 4
  → memo[0][4] = 4 ✓

Result: 4

Memoization Table:

For "bbbab":

memo[i][j]:
     0    1    2    3    4
0 [  -    -    -    -    4 ]  helper(0,4) → 4
1 [       -    2    2    - ]  helper(1,2) → 2, helper(1,3) → 2
2 [            1    1    - ]  helper(2,2) → 1, helper(2,3) → 1
3 [                 1    - ]  helper(3,3) → 1
4 [                      1 ]  (base case, never stored)

Each cell computed exactly once!

Execution Order:

helper(3,3) → 1 (base case)
helper(2,2) → 1 (base case)
helper(2,3) → max(1, 1) = 1 (store memo[2][3] = 1)
helper(2,1) → 0 (base case)
helper(1,2) → 2 + 0 = 2 (store memo[1][2] = 2)
helper(1,3) → max(1, 2) = 2 (store memo[1][3] = 2)
helper(0,4) → 2 + 2 = 4 (store memo[0][4] = 4)

Total computations: O(n²) instead of O(2^n)!

Complexity:

Time: O(n²) - n² subproblems, each computed once
Space: O(n²) - memo table + O(n) recursion stack

3. Bottom-Up DP (Tabulation - O(n²))

The Intuition

Key Insight: Build solutions from small ranges to large ranges.

Build order:

Length 1: Single characters (length = 1)
Length 2: Two characters (check if they match)
Length 3+: Use previously computed smaller ranges

State: dp[i][j] = length of longest palindromic subsequence in s[i...j]

Transition:

if (s[i] == s[j]):
    dp[i][j] = 2 + dp[i+1][j-1]
else:
    dp[i][j] = max(dp[i+1][j], dp[i][j-1])

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    // Base case: single character
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Build by increasing length
    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] = 2 + (len == 2 ? 0 : dp[i+1][j-1]);
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    return dp[0][n-1];
}

What Happens with `s = "bbbab"`:

Step 1: Initialize single characters (length 1)
dp[0][0] = 1  // "b"
dp[1][1] = 1  // "b"
dp[2][2] = 1  // "b"
dp[3][3] = 1  // "a"
dp[4][4] = 1  // "b"

Step 2: Process length 2
i=0, j=1: "bb"
  s[0] == s[1]? 'b' == 'b' ✓
  → dp[0][1] = 2 + 0 = 2

i=1, j=2: "bb"
  s[1] == s[2]? 'b' == 'b' ✓
  → dp[1][2] = 2 + 0 = 2

i=2, j=3: "ba"
  s[2] == s[3]? 'b' == 'a' ✗
  → dp[2][3] = max(dp[3][3], dp[2][2]) = max(1, 1) = 1

i=3, j=4: "ab"
  s[3] == s[4]? 'a' == 'b' ✗
  → dp[3][4] = max(dp[4][4], dp[3][3]) = max(1, 1) = 1

Step 3: Process length 3
i=0, j=2: "bbb"
  s[0] == s[2]? 'b' == 'b' ✓
  → dp[0][2] = 2 + dp[1][1] = 2 + 1 = 3

i=1, j=3: "bba"
  s[1] == s[3]? 'b' == 'a' ✗
  → dp[1][3] = max(dp[2][3], dp[1][2]) = max(1, 2) = 2

i=2, j=4: "bab"
  s[2] == s[4]? 'b' == 'b' ✓
  → dp[2][4] = 2 + dp[3][3] = 2 + 1 = 3

Step 4: Process length 4
i=0, j=3: "bbba"
  s[0] == s[3]? 'b' == 'a' ✗
  → dp[0][3] = max(dp[1][3], dp[0][2]) = max(2, 3) = 3

i=1, j=4: "bbab"
  s[1] == s[4]? 'b' == 'b' ✓
  → dp[1][4] = 2 + dp[2][3] = 2 + 1 = 3

Step 5: Process length 5
i=0, j=4: "bbbab"
  s[0] == s[4]? 'b' == 'b' ✓
  → dp[0][4] = 2 + dp[1][3] = 2 + 2 = 4 ✓

Result: dp[0][4] = 4

DP Table Evolution:

Initial (length 1):
  1    2    3    4
[  1    -    -    -    - ]
[       1    -    -    - ]
[            1    -    - ]
[                 1    - ]
[                      1 ]

After length 2:
  1    2    3    4
[  1    2    -    -    - ]
[       1    2    -    - ]
[            1    1    - ]
[                 1    1 ]
[                      1 ]

After length 3:
  1    2    3    4
[  1    2    3    -    - ]
[       1    2    2    - ]
[            1    1    3 ]
[                 1    1 ]
[                      1 ]

After length 4:
  1    2    3    4
[  1    2    3    3    - ]
[       1    2    2    3 ]
[            1    1    3 ]
[                 1    1 ]
[                      1 ]

Final (length 5):
  1    2    3    4
[  1    2    3    3    4 ] ← Answer: dp[0][4] = 4
[       1    2    2    3 ]
[            1    1    3 ]
[                 1    1 ]
[                      1 ]

Step-by-step with `s = "cbbd"`:

Step 1: Single characters
dp[0][0] = 1  // "c"
dp[1][1] = 1  // "b"
dp[2][2] = 1  // "b"
dp[3][3] = 1  // "d"

Step 2: Length 2
i=0, j=1: "cb" → 'c' != 'b' → max(dp[1][1], dp[0][0]) = 1
i=1, j=2: "bb" → 'b' == 'b' → 2 + 0 = 2 ✓
i=2, j=3: "bd" → 'b' != 'd' → max(dp[3][3], dp[2][2]) = 1

Step 3: Length 3
i=0, j=2: "cbb" → 'c' != 'b' → max(dp[1][2], dp[0][1]) = max(2, 1) = 2
i=1, j=3: "bbd" → 'b' != 'd' → max(dp[2][3], dp[1][2]) = max(1, 2) = 2

Step 4: Length 4
i=0, j=3: "cbbd" → 'c' != 'd' → max(dp[1][3], dp[0][2]) = max(2, 2) = 2 ✓

Result: 2 (subsequence "bb")

Complexity:

Time: O(n²) - two nested loops
Space: O(n²) - dp table only (no recursion stack)

Quick Comparison

Feature	Pure Recursion	Memoization	Tabulation
Structure	Recursive	Recursive + cache	Loop + array
Direction	Top-down	Top-down	Bottom-up
Time	O(2^n)	O(n²)	O(n²)
Space	O(n) stack	O(n²) memo + O(n) stack	O(n²) array only
Intuition	"Match ends or skip one"	"Cache recursive results"	"Build small → large"
When to use	Never (too slow)	Natural recursion	Fastest, most efficient

The Evolution

Approach 1 → Approach 2:

// Add memoization to recursive solution
if (memo[i][j] != null) return memo[i][j];

int result = ... // compute
memo[i][j] = result;
return result;

Approach 2 → Approach 3:

// Replace recursion with nested loops
for len = 2 to n:
    for i = 0 to n-len:
        j = i + len - 1
        if (s[i] == s[j]):
            dp[i][j] = 2 + dp[i+1][j-1]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Mental Models

Pure Recursion: "At each step, if ends match, include both. Otherwise, try skipping left or right. This creates a branching tree of possibilities."

Memoization: "Same recursive thinking, but I'll write down results so I don't recompute. The tree becomes a DAG (directed acyclic graph)."

Tabulation: "Let me systematically solve all small ranges first, then use them to build solutions for larger ranges. No recursion needed."

Which Approach to Use?

Use Pure Recursion when:

❌ Never in production - too slow (O(2^n))
✅ Only for understanding the problem initially
✅ Helps visualize the recursive structure

Use Memoization when:

✅ You want to think recursively
✅ The recursive structure helps you understand the problem
✅ You're converting a recursive solution to DP

Use Tabulation when:

✅ You want the most efficient solution
✅ You want to avoid recursion overhead
✅ You're comfortable with interval DP patterns
✅ Production code - fastest execution

Complete Working Example

public class LongestPalindromicSubsequence {

    // Approach 1: Pure Recursion (SLOW - for understanding only)
    public int longestPalindromeSubseqRecursive(String s) {
        return helperRecursive(s, 0, s.length() - 1);
    }

    private int helperRecursive(String s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;

        if (s.charAt(i) == s.charAt(j)) {
            return 2 + helperRecursive(s, i + 1, j - 1);
        }

        int skipLeft = helperRecursive(s, i + 1, j);
        int skipRight = helperRecursive(s, i, j - 1);
        return Math.max(skipLeft, skipRight);
    }

    // Approach 2: Memoization
    public int longestPalindromeSubseqMemo(String s) {
        int n = s.length();
        Integer[][] memo = new Integer[n][n];
        return helperMemo(s, 0, n - 1, memo);
    }

    private int helperMemo(String s, int i, int j, Integer[][] memo) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (memo[i][j] != null) return memo[i][j];

        int result;
        if (s.charAt(i) == s.charAt(j)) {
            result = 2 + helperMemo(s, i + 1, j - 1, memo);
        } else {
            int skipLeft = helperMemo(s, i + 1, j, memo);
            int skipRight = helperMemo(s, i, j - 1, memo);
            result = Math.max(skipLeft, skipRight);
        }

        memo[i][j] = result;
        return result;
    }

    // Approach 3: Tabulation
    public int longestPalindromeSubseqDP(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        // Single characters
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Build by length
        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] = 2 + (len == 2 ? 0 : dp[i+1][j-1]);
                } 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) {
        LongestPalindromicSubsequence lps = new LongestPalindromicSubsequence();

        System.out.println("Test 1: 'bbbab'");
        System.out.println("Pure Recursion: " + lps.longestPalindromeSubseqRecursive("bbbab")); // 4
        System.out.println("Memoization: " + lps.longestPalindromeSubseqMemo("bbbab"));           // 4
        System.out.println("Tabulation: " + lps.longestPalindromeSubseqDP("bbbab"));              // 4

        System.out.println("\nTest 2: 'cbbd'");
        System.out.println("Pure Recursion: " + lps.longestPalindromeSubseqRecursive("cbbd")); // 2
        System.out.println("Memoization: " + lps.longestPalindromeSubseqMemo("cbbd"));           // 2
        System.out.println("Tabulation: " + lps.longestPalindromeSubseqDP("cbbd"));              // 2
    }
}

Common Pitfalls

Pitfall 1: Confusing substring vs subsequence

// WRONG - this is for SUBSTRING (contiguous)
dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]  // boolean

// RIGHT - this is for SUBSEQUENCE (can skip)
if (s[i] == s[j]):
    dp[i][j] = 2 + dp[i+1][j-1]  // integer length
else:
    dp[i][j] = max(dp[i+1][j], dp[i][j-1])  // try skipping

Pitfall 2: Wrong base case handling

// WRONG - accessing out of bounds
if (s.charAt(i) == s.charAt(j)) {
    dp[i][j] = 2 + dp[i+1][j-1];  // What if j-1 < i+1?
}

// RIGHT - handle length 2 specially
if (s.charAt(i) == s.charAt(j)) {
    dp[i][j] = 2 + (len == 2 ? 0 : dp[i+1][j-1]);
}

Pitfall 3: Wrong iteration order in tabulation

// WRONG - may use uncomputed values
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        dp[i][j] = ... dp[i+1][j-1];  // i+1 not computed yet!
    }
}

// RIGHT - build by increasing length
for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        // now dp[i+1][j-1] is already computed
    }
}

Practice Extensions

Once you master these three approaches, try:

Minimum Insertions to Make String Palindrome (LC 1312): n - longestPalindromeSubseq
Longest Common Subsequence (LC 1143): Similar DP structure
Edit Distance (LC 72): Classic DP with similar transitions
Palindrome Partitioning II (LC 132): Combine with palindrome checking

Problem	Type	Goal	Contiguous?	State
Longest Palindromic Substring	Optimization	Find longest	✅ Yes	`dp[i][j]` = boolean
Palindromic Substrings	Counting	Count all	✅ Yes	Count during check
Longest Palindromic Subsequence	Optimization	Find longest	❌ No	`dp[i][j]` = length

Critical difference: Subsequence allows skipping characters!

Key Takeaways

THE SUBSEQUENCE PATTERN

Pure Recursion: Understand the recursive structure

Think: "Match ends → include both; else → try skipping each"
Use: Only for initial understanding

Memoization: Add caching to recursion

Think: "Same recursion, but remember results"
Use: When recursion feels natural

Tabulation: Build systematically from base cases

Think: "Small ranges → large ranges, no recursion"
Use: Production code, most efficient

Key insight: Subsequence allows skipping → different transition than substring!

The Big Picture

Longest Palindromic Subsequence is a classic interval DP problem with the subsequence twist.

Master it, and you'll understand:

The difference between substring and subsequence
How to handle "skip one side" transitions
Progressive optimization from O(2^n) → O(n²)
Multiple approaches to the same DP problem

This is your subsequence foundation. Build it strong.

Understanding the Problem​

1. Pure Recursion (Unoptimized - O(2^n))​

The Intuition​

What Happens with s = "bbbab":​

Call Tree Visualization:​

Why is it Slow?​

Complexity:​

2. Top-Down DP (Memoization - O(n²))​

The Intuition​

What Happens with s = "bbbab":​

Memoization Table:​

Execution Order:​

Complexity:​

3. Bottom-Up DP (Tabulation - O(n²))​

The Intuition​

What Happens with s = "bbbab":​

DP Table Evolution:​

Step-by-step with s = "cbbd":​

Complexity:​

Quick Comparison​

The Evolution​

Approach 1 → Approach 2:​

Approach 2 → Approach 3:​

Mental Models​

Which Approach to Use?​

Use Pure Recursion when:​

Use Memoization when:​

Use Tabulation when:​

Complete Working Example​

Common Pitfalls​

Pitfall 1: Confusing substring vs subsequence​

Pitfall 2: Wrong base case handling​

Pitfall 3: Wrong iteration order in tabulation​

Practice Extensions​

Key Differences from Related Problems​

Key Takeaways​

The Big Picture​

Understanding the Problem

1. Pure Recursion (Unoptimized - O(2^n))

The Intuition

What Happens with `s = "bbbab"`:

Call Tree Visualization:

Why is it Slow?

Complexity:

2. Top-Down DP (Memoization - O(n²))

The Intuition

What Happens with `s = "bbbab"`:

Memoization Table:

Execution Order:

Complexity:

3. Bottom-Up DP (Tabulation - O(n²))

The Intuition

What Happens with `s = "bbbab"`:

DP Table Evolution:

Step-by-step with `s = "cbbd"`:

Complexity:

Quick Comparison

The Evolution

Approach 1 → Approach 2:

Approach 2 → Approach 3:

Mental Models

Which Approach to Use?

Use Pure Recursion when:

Use Memoization when:

Use Tabulation when:

Complete Working Example

Common Pitfalls

Pitfall 1: Confusing substring vs subsequence

Pitfall 2: Wrong base case handling

Pitfall 3: Wrong iteration order in tabulation

Practice Extensions

Key Differences from Related Problems

Key Takeaways

The Big Picture