Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest Palindromic Subsequence

MEDIUMProblemSolveExternal Links

Description

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 is a string that reads the same forward and backward.

For example, in the string "bbbab", the subsequence "bbbb" is a palindrome of length 4. Note that a subsequence does not need to be contiguous — the characters can be picked from any positions as long as their relative order is preserved.

Examples

Example 1

Input: s = "bbbab"

Output: 4

Explanation: One possible longest palindromic subsequence is "bbbb". We can pick the characters at indices 0, 1, 2, and 4 (all 'b's) to form this palindrome. Although index 3 ('a') is skipped, the remaining characters still maintain their original order and form a valid palindrome of length 4.

Example 2

Input: s = "cbbd"

Output: 2

Explanation: One possible longest palindromic subsequence is "bb". We pick the characters at indices 1 and 2. No longer palindromic subsequence exists in this string — any subsequence of length 3 or more cannot form a palindrome.

Example 3

Input: s = "a"

Output: 1

Explanation: A single character is always a palindrome by itself. The longest palindromic subsequence is "a" with length 1.

Constraints

  • 1 ≤ s.length ≤ 1000
  • s consists only of lowercase English letters.

Editorial

Brute Force

Intuition

The most straightforward way to find the longest palindromic subsequence is to use recursion. We place two pointers — one at the beginning and one at the end of the string — and try to build a palindrome from the outside in.

Think of it like holding a book open at both ends and comparing the first and last letters. If they match, both letters are part of our palindrome, and we move inward. If they do not match, we have two choices: skip the letter on the left, or skip the letter on the right. We try both options and keep whichever gives a longer palindrome.

This recursive exploration examines every possible combination of keeping or skipping characters, which is why it is called brute force — it generates all possible subsequences implicitly and finds the longest palindromic one.

Step-by-Step Explanation

Let's trace through with s = "cbbd":

Step 1: Start with low=0 ('c'), high=3 ('d'). Compare s[0] and s[3]: 'c' ≠ 'd'. They don't match, so we branch into two recursive calls.

Step 2: Branch A — skip the left character: solve for low=1, high=3 (substring "bbd"). Compare s[1]='b' and s[3]='d': 'b' ≠ 'd'. Branch again.

Step 3: Branch A1 — skip left: solve for low=2, high=3 ("bd"). s[2]='b' ≠ s[3]='d'. Branch again.

Step 4: Branch A1a — skip left: low=3, high=3 ("d"). Single character → return 1.

Step 5: Branch A1b — skip right: low=2, high=2 ("b"). Single character → return 1.

Step 6: Back at Branch A1: max(1, 1) = 1.

Step 7: Branch A2 — skip right: solve for low=1, high=2 ("bb"). s[1]='b' == s[2]='b'. Characters match! Return 2 + solve(low=2, high=1). Since low > high, base case returns 0. So result = 2 + 0 = 2.

Step 8: Back at Branch A: max(1, 2) = 2.

Step 9: Branch B — skip the right character from the original call: solve for low=0, high=2 ("cbb"). s[0]='c' ≠ s[2]='b'. Branch again.

Step 10: Branch B eventually computes max values from its sub-branches and returns 2 (finding "bb" again).

Step 11: Back at the root: max(Branch A = 2, Branch B = 2) = 2.

Result: The longest palindromic subsequence has length 2.

Recursive Exploration of Palindromic Subsequences — Watch how the recursion branches at each mismatch, exploring all possibilities of skipping the left or right character until matches or base cases are found.

Algorithm

  1. Define a recursive function lps(s, low, high) that returns the length of the longest palindromic subsequence in s[low..high].
  2. Base cases:
    • If low > high, return 0 (empty substring).
    • If low == high, return 1 (single character is always a palindrome).
  3. Recursive cases:
    • If s[low] == s[high], both characters belong to the palindrome. Return 2 + lps(s, low+1, high-1).
    • If s[low] != s[high], skip one character from either end. Return max(lps(s, low+1, high), lps(s, low, high-1)).
  4. Call lps(s, 0, n-1) where n is the length of the string.

Code

class Solution {
public:
    int lps(string& s, int low, int high) {
        if (low > high) return 0;
        if (low == high) return 1;
        
        if (s[low] == s[high])
            return 2 + lps(s, low + 1, high - 1);
        
        return max(lps(s, low + 1, high), lps(s, low, high - 1));
    }
    
    int longestPalindromeSubseq(string s) {
        return lps(s, 0, s.size() - 1);
    }
};
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        def lps(low: int, high: int) -> int:
            if low > high:
                return 0
            if low == high:
                return 1
            
            if s[low] == s[high]:
                return 2 + lps(low + 1, high - 1)
            
            return max(lps(low + 1, high), lps(low, high - 1))
        
        return lps(0, len(s) - 1)
class Solution {
    public int longestPalindromeSubseq(String s) {
        return lps(s, 0, s.length() - 1);
    }
    
    private int lps(String s, int low, int high) {
        if (low > high) return 0;
        if (low == high) return 1;
        
        if (s.charAt(low) == s.charAt(high))
            return 2 + lps(s, low + 1, high - 1);
        
        return Math.max(lps(s, low + 1, high), lps(s, low, high - 1));
    }
}

Complexity Analysis

Time Complexity: O(2^n)

In the worst case (when no characters match, like "abcd"), each call branches into two recursive calls. The recursion tree has depth n and can have up to 2^n nodes. This is because at each level, we either skip the left or right character, leading to an exponential explosion of subproblems.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one level per character in the worst case). No additional data structures are used beyond the call stack.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(2^n). For a string of length 1000 (the maximum constraint), 2^1000 is astronomically large — far beyond what any computer can process within time limits.

The root cause is overlapping subproblems. The same substring range (low, high) gets computed multiple times through different recursive paths. For example, lps(2, 5) might be called from both lps(1, 5) (skipping left) and lps(2, 6) (skipping right). This redundant computation grows exponentially.

The key insight: there are only O(n²) unique (low, high) pairs. If we store the result of each pair the first time we compute it and reuse it later, we eliminate all redundant work. This is the foundation of dynamic programming — memoization.

Better Approach - Memoization (Top-Down DP)

Intuition

The recursive brute force computes the same subproblems over and over. Memoization fixes this by adding a "memory" — a 2D table where dp[low][high] stores the result of lps(low, high) once computed.

Imagine you are solving a jigsaw puzzle. Without memoization, every time you need a specific piece, you search the entire pile from scratch. With memoization, once you find a piece, you place it on the table where you can instantly grab it next time.

The recursive logic stays identical — we just add a lookup before each computation and a store after each result. This single optimization drops the time from O(2^n) to O(n²).

Step-by-Step Explanation

Let's trace through with s = "cbbd" using memoization:

Step 1: Initialize a 4×4 memo table with all values set to -1 (uncomputed).

Step 2: Call lps(0, 3). s[0]='c' ≠ s[3]='d'. Not in memo. Branch into lps(1,3) and lps(0,2).

Step 3: Call lps(1, 3). s[1]='b' ≠ s[3]='d'. Not in memo. Branch into lps(2,3) and lps(1,2).

Step 4: Call lps(1, 2). s[1]='b' == s[2]='b'. Match! Result = 2 + lps(2,1) = 2 + 0 = 2. Store dp[1][2] = 2.

Step 5: Call lps(2, 3). s[2]='b' ≠ s[3]='d'. Branch into lps(3,3)=1 and lps(2,2)=1. Result = max(1,1) = 1. Store dp[2][3] = 1.

Step 6: Back at lps(1,3): max(dp[2][3], dp[1][2]) = max(1, 2) = 2. Store dp[1][3] = 2.

Step 7: Call lps(0, 2). s[0]='c' ≠ s[2]='b'. Branch into lps(1,2) and lps(0,1).

Step 8: lps(1,2) is already in memo! dp[1][2] = 2. No recomputation needed. This is where memoization saves work.

Step 9: Call lps(0, 1). s[0]='c' ≠ s[1]='b'. Branch into lps(1,1)=1 and lps(0,0)=1. Result = 1. Store dp[0][1] = 1.

Step 10: Back at lps(0,2): max(dp[1][2], dp[0][1]) = max(2, 1) = 2. Store dp[0][2] = 2.

Step 11: Back at root lps(0,3): max(dp[1][3], dp[0][2]) = max(2, 2) = 2. Store dp[0][3] = 2.

Result: dp[0][3] = 2. The memo prevented recomputation of lps(1,2).

Algorithm

  1. Create an n×n table dp initialized to -1.
  2. Define recursive function lps(s, low, high, dp):
    • If low > high, return 0.
    • If low == high, return 1.
    • If dp[low][high] != -1, return the cached value (already computed).
    • If s[low] == s[high], set dp[low][high] = 2 + lps(s, low+1, high-1, dp).
    • Otherwise, set dp[low][high] = max(lps(s, low+1, high, dp), lps(s, low, high-1, dp)).
    • Return dp[low][high].
  3. Call lps(s, 0, n-1, dp).

Code

class Solution {
public:
    int lps(string& s, int low, int high, vector<vector<int>>& dp) {
        if (low > high) return 0;
        if (low == high) return 1;
        if (dp[low][high] != -1) return dp[low][high];
        
        if (s[low] == s[high])
            return dp[low][high] = 2 + lps(s, low + 1, high - 1, dp);
        
        return dp[low][high] = max(lps(s, low + 1, high, dp), lps(s, low, high - 1, dp));
    }
    
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        return lps(s, 0, n - 1, dp);
    }
};
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[-1] * n for _ in range(n)]
        
        def lps(low: int, high: int) -> int:
            if low > high:
                return 0
            if low == high:
                return 1
            if dp[low][high] != -1:
                return dp[low][high]
            
            if s[low] == s[high]:
                dp[low][high] = 2 + lps(low + 1, high - 1)
            else:
                dp[low][high] = max(lps(low + 1, high), lps(low, high - 1))
            
            return dp[low][high]
        
        return lps(0, n - 1)
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, -1);
        return lps(s, 0, n - 1, dp);
    }
    
    private int lps(String s, int low, int high, int[][] dp) {
        if (low > high) return 0;
        if (low == high) return 1;
        if (dp[low][high] != -1) return dp[low][high];
        
        if (s.charAt(low) == s.charAt(high))
            dp[low][high] = 2 + lps(s, low + 1, high - 1, dp);
        else
            dp[low][high] = Math.max(lps(s, low + 1, high, dp), lps(s, low, high - 1, dp));
        
        return dp[low][high];
    }
}

Complexity Analysis

Time Complexity: O(n²)

There are n² unique (low, high) pairs. Each pair is computed exactly once and cached. Each computation does O(1) work (a comparison and at most two lookups). So the total work is O(n²).

Space Complexity: O(n²)

The memoization table has n×n entries. Additionally, the recursion stack can go up to O(n) deep. The dominant space cost is the n² table.

Why This Approach Is Not Efficient

While memoization dramatically reduces time from O(2^n) to O(n²), it still uses O(n²) space for the memo table plus O(n) for the recursion call stack. For n = 1000, this means a million-entry table plus potentially deep recursion that could cause stack overflow in some languages.

The recursive overhead (function call costs, stack frame allocation) also adds a constant factor. We can eliminate both the recursion overhead and the stack space risk by converting the top-down recursion into a bottom-up iterative approach — tabulation. Furthermore, once we use tabulation, we can observe that each row of the DP table only depends on the row below it, enabling space optimization from O(n²) down to O(n).

Optimal Approach - Bottom-Up DP (Tabulation with Space Optimization)

Intuition

Instead of starting from the full string and recursing down (top-down), we start from the smallest substrings and build up (bottom-up). We define dp[i][j] as the length of the longest palindromic subsequence in the substring s[i..j].

Think of building a pyramid from the bottom. The base layer consists of single characters (each is a palindrome of length 1). The next layer combines pairs of adjacent characters. Each subsequent layer considers longer substrings, using already-computed results from shorter ones.

The recurrence is the same as the recursive approach:

  • If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
  • If s[i] != s[j]: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The critical space optimization: when computing row i, we only need values from row i+1 (the previous row in our iteration). So we can use just two 1D arrays instead of a full 2D table, reducing space from O(n²) to O(n).

Step-by-Step Explanation

Let's trace through with s = "bbbab" (n=5) using bottom-up tabulation:

We fill the DP table diagonally, starting from single characters (length 1 substrings), then length 2, then length 3, etc.

Step 1: Initialize: Every single character is a palindrome of length 1. dp[i][i] = 1 for all i. So dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1, dp[4][4]=1.

Step 2: Length 2 substrings. dp[0][1]: s[0]='b', s[1]='b'. Match! dp[0][1] = dp[1][0] + 2 = 0 + 2 = 2.

Step 3: dp[1][2]: s[1]='b', s[2]='b'. Match! dp[1][2] = dp[2][1] + 2 = 0 + 2 = 2.

Step 4: dp[2][3]: s[2]='b', s[3]='a'. No match. dp[2][3] = max(dp[3][3], dp[2][2]) = max(1, 1) = 1.

Step 5: dp[3][4]: s[3]='a', s[4]='b'. No match. dp[3][4] = max(dp[4][4], dp[3][3]) = max(1, 1) = 1.

Step 6: Length 3 substrings. dp[0][2]: s[0]='b', s[2]='b'. Match! dp[0][2] = dp[1][1] + 2 = 1 + 2 = 3.

Step 7: dp[1][3]: s[1]='b', s[3]='a'. No match. dp[1][3] = max(dp[2][3], dp[1][2]) = max(1, 2) = 2.

Step 8: dp[2][4]: s[2]='b', s[4]='b'. Match! dp[2][4] = dp[3][3] + 2 = 1 + 2 = 3.

Step 9: Length 4 substrings. dp[0][3]: s[0]='b', s[3]='a'. No match. dp[0][3] = max(dp[1][3], dp[0][2]) = max(2, 3) = 3.

Step 10: dp[1][4]: s[1]='b', s[4]='b'. Match! dp[1][4] = dp[2][3] + 2 = 1 + 2 = 3.

Step 11: Length 5 (full string). dp[0][4]: s[0]='b', s[4]='b'. Match! dp[0][4] = dp[1][3] + 2 = 2 + 2 = 4.

Result: dp[0][4] = 4. The longest palindromic subsequence in "bbbab" has length 4.

Bottom-Up DP Table Fill for LPS of "bbbab" — Watch how we fill the DP table from single characters (diagonal) outward to longer substrings, building the answer from smaller solved subproblems.

Algorithm

  1. Create two 1D arrays prev and curr of size n, initialized to 0.
  2. Iterate i from n-1 down to 0 (processing rows bottom-up):
    a. Set curr[i] = 1 (base case: single character).
    b. For each j from i+1 to n-1:
    • If s[i] == s[j]: curr[j] = prev[j-1] + 2
    • Else: curr[j] = max(prev[j], curr[j-1])
      c. Copy curr into prev for the next iteration.
  3. Return prev[n-1] (which stores dp[0][n-1]).

Code

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<int> prev(n, 0), curr(n, 0);
        
        for (int i = n - 1; i >= 0; i--) {
            curr[i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    curr[j] = prev[j - 1] + 2;
                } else {
                    curr[j] = max(prev[j], curr[j - 1]);
                }
            }
            prev = curr;
        }
        
        return prev[n - 1];
    }
};
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        prev = [0] * n
        curr = [0] * n
        
        for i in range(n - 1, -1, -1):
            curr[i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    curr[j] = prev[j - 1] + 2
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev = curr[:]
        
        return prev[n - 1]
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[] prev = new int[n];
        int[] curr = new int[n];
        
        for (int i = n - 1; i >= 0; i--) {
            curr[i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    curr[j] = prev[j - 1] + 2;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            System.arraycopy(curr, 0, prev, 0, n);
        }
        
        return prev[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n²)

We have two nested loops: the outer loop runs n times (for each starting index i), and the inner loop runs up to n times (for each ending index j). Each cell computation involves a single comparison and constant-time operations. Total: O(n²).

Space Complexity: O(n)

Instead of storing the full n×n DP table, we only maintain two arrays of size n (prev and curr). At each step of the outer loop, the current row only depends on the previous row. This space optimization reduces memory from O(n²) to O(n), which is significant for n = 1000 (from ~1 million entries down to ~2000).