Longest Palindromic Subsequence

Problem Statement

Given a string s, find the length of the longest palindromic subsequence in it. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A palindrome reads the same forwards and backwards.

Example:

• Input: s = "bbbab"
• Output: 4
• Explanation: The longest palindromic subsequence is "bbbb" which has length 4.

Noob-Friendly Explanation

Imagine you have a string of colored beads on a table. You can remove some beads (but you can't rearrange the remaining ones). Your goal is to keep as many beads as possible such that the remaining beads form a pattern that looks the same from the left and from the right — like a mirror image.

For example, with beads b-b-b-a-b, you can remove the a to get b-b-b-b, which reads the same forwards and backwards. That's 4 beads — the longest palindromic subsequence.

Approach 1: Brute Force (Recursion)

Intuition

We try every possible subsequence using recursion. We compare characters from the start and end of the string. If they match, they're part of our palindrome. If they don't match, we try skipping one character from either end and pick the better option.

Algorithm

1. Use two pointers i (start) and j (end) of the string.
2. If s[i] == s[j], both characters are in the palindrome — add 2 and move both pointers inward.
3. If they don't match, try two options: skip i or skip j, and take the maximum.
4. Base case: if i == j, return 1 (single character is a palindrome). If i > j, return 0.

class Solution {
    public int longestPalinSubseq(String s) {
        return solve(s, 0, s.length() - 1);
    }

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

        if (s.charAt(i) == s.charAt(j)) {
            return 2 + solve(s, i + 1, j - 1);
        } else {
            return Math.max(solve(s, i + 1, j), solve(s, i, j - 1));
        }
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - In the worst case, each call branches into two recursive calls, leading to exponential time.
• Space Complexity: O(n) - The recursion stack can go as deep as n.

Approach 2: Optimal (Dynamic Programming)

Intuition

The brute force recalculates the same subproblems many times. We use a 2D DP table where dp[i][j] stores the length of the longest palindromic subsequence in the substring s[i..j]. We fill this table bottom-up.

Algorithm

1. Create a 2D array dp of size n x n. Every single character is a palindrome of length 1, so dp[i][i] = 1.
2. Fill the table for increasing lengths of substrings.
3. For each substring s[i..j]: if s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2. Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
4. The answer is in dp[0][n-1].

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

        // Every single character is a palindrome of length 1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // Fill for substrings of length 2 to n
        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] = 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];
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - We fill an n×n table, and each cell takes O(1) time.
• Space Complexity: O(n^2) - We use a 2D array of size n×n.