Longest Palindromic Subsequence - Get Subsequence | K5kC

Problem

Given a string s, find the longest palindromic subsequence in it. Return the actual subsequence (not just its length).

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

Examples

Example 1

1
2
3
4
5
6


Input:
s = "BBABCBCAB"
Output:
"BABCBAB"
Explanation:
The longest palindromic subsequence is "BABCBAB" (other valid answers: "BACBCAB").

Example 2

1
2
3
4
5
6


Input:
s = "agbdba"
Output:
"abdba"
Explanation:
The longest palindromic subsequence is "abdba".

Solution

Palindromic subsequences are sequences within a string that read the same forwards and backwards, but do not require the characters to be contiguous. The challenge is to find the longest such subsequence, not just its length, but the actual sequence itself.

A simple way to check if a string is a palindrome is to use two pointers at each end and compare characters while moving inward. For subsequences, however, we need to consider all possible ways to delete characters and still maintain the order, which makes the problem more complex than checking substrings. For e.g. checkout Longest Common Subsequence Problem.

Method 1 - Naive

The naive approach is to generate all possible subsequences and check each for being a palindrome, and find the longest among them as the answer. This solution is exponential in term of time complexity. Also, as there are so many sub sequences to evaluate, approx 2^N where N is the number of characters in the given string.

Complexity

⏰ Time complexity: O(2^N * N) — There are 2^N possible subsequences, and checking each for being a palindrome takes up to O(N) time.
🧺 Space complexity: O(N) — Space needed for storing a single subsequence during checking.

Method 2 - Recursion

This function returns length:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


int **lps**(char *seq, int i, int j) {
 // Base Case 1: If there is only 1 character
 if (i == j)
 return 1;

 // Base Case 2: If there are only 2 characters and both are same
 if (seq[i] == seq[j] && i + 1 == j)
 return 2;

 // If the first and last characters match
 if (seq[i] == seq[j])
 return **lps** (seq, i+1, j-1) + 2;

 // If the first and last characters do not match
 return max( **lps**(seq, i, j-1), **lps**(seq, i+1, j) );
}

Here is the substructure of recursion:

1
2
3
4
5
6
7


 L(0, 5)
 /        \
 /          \ 
 L(1,5)          L(0,4)
 /    \            /    \
 /      \          /      \
 L(2,5)    L(1,4)  L(1,4)  L(0,3)

In the above partial recursion tree, L(1, 4) is being solved twice. So, we have overlapping subproblems.

Method 2 – Recursive Approach

Intuition

The recursive approach explores all possible ways to form a palindromic subsequence by comparing characters at both ends of the string. If the characters match, they are included in the subsequence; otherwise, we recursively check by excluding one character from either end. This method builds the solution by breaking the problem into smaller subproblems.

Approach

Define a recursive function that takes the string and two indices (start and end).
If the start index exceeds the end index, return an empty string.
If the start index equals the end index, return the single character (base case).
If the characters at start and end match, include them and recurse for the inner substring.
If they do not match, recursively find the longest palindromic subsequence by excluding either the start or end character, and return the longer result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    public String longestPalindromicSubsequence(String s, int i, int j) {
        if (i > j) return "";
        if (i == j) return Character.toString(s.charAt(i));
        if (s.charAt(i) == s.charAt(j)) {
            return s.charAt(i) + longestPalindromicSubsequence(s, i+1, j-1) + s.charAt(j);
        }
        String left = longestPalindromicSubsequence(s, i+1, j);
        String right = longestPalindromicSubsequence(s, i, j-1);
        return left.length() > right.length() ? left : right;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def longest_palindromic_subsequence(s: str, i: int, j: int) -> str:
    if i > j:
        return ""
    if i == j:
        return s[i]
    if s[i] == s[j]:
        return s[i] + longest_palindromic_subsequence(s, i+1, j-1) + s[j]
    left = longest_palindromic_subsequence(s, i+1, j)
    right = longest_palindromic_subsequence(s, i, j-1)
    return left if len(left) > len(right) else right

Complexity

⏰ Time complexity: O(2^N) — Each character can be either included or excluded, leading to exponential subproblems.
🧺 Space complexity: O(N) — Space for the recursion stack and storing the subsequence.

Method 3 – Top Down DP (Memoization)

Intuition

The memoized top-down approach improves upon the plain recursion by storing results of subproblems in a cache (memoization table). This avoids redundant calculations and speeds up the process, especially for overlapping subproblems.

Approach

Use a recursive function similar to Method 2, but add a memoization table (2D array or map) to store results for each (i, j) pair.
Before computing a result for (i, j), check if it is already in the memo table and return it if so.
Otherwise, compute as in Method 2:
- If s[i] == s[j], include both and recurse for (i+1, j-1).
- Else, recurse for (i+1, j) and (i, j-1), and take the longer result.
Store the result in the memo table before returning.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def longest_palindromic_subsequence_memo(s: str) -> str:
    memo = {}
    def dp(i: int, j: int) -> str:
        if i > j:
            return ""
        if i == j:
            return s[i]
        if (i, j) in memo:
            return memo[(i, j)]
        if s[i] == s[j]:
            memo[(i, j)] = s[i] + dp(i+1, j-1) + s[j]
        else:
            left = dp(i+1, j)
            right = dp(i, j-1)
            memo[(i, j)] = left if len(left) > len(right) else right
        return memo[(i, j)]
    return dp(0, len(s)-1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import java.util.HashMap;
import java.util.Map;
class Solution {
    private Map<String, String> memo = new HashMap<>();
    public String longestPalindromicSubsequenceMemo(String s, int i, int j) {
        if (i > j) return "";
        if (i == j) return Character.toString(s.charAt(i));
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        if (s.charAt(i) == s.charAt(j)) {
            memo.put(key, s.charAt(i) + longestPalindromicSubsequenceMemo(s, i+1, j-1) + s.charAt(j));
        } else {
            String left = longestPalindromicSubsequenceMemo(s, i+1, j);
            String right = longestPalindromicSubsequenceMemo(s, i, j-1);
            memo.put(key, left.length() > right.length() ? left : right);
        }
        return memo.get(key);
    }
}

Complexity

⏰ Time complexity: O(N^2) — There are O(N^2) unique subproblems, each solved once.
🧺 Space complexity: O(N^2) — Space for the memoization table and recursion stack.

Method 4 – Bottom-Up DP (Tabulation)

Intuition

The bottom-up dynamic programming approach builds a solution by solving smaller subproblems first and using their results to solve larger ones. We fill a DP table where each cell represents the longest palindromic subsequence for a substring, and then reconstruct the actual subsequence from the table. This method is efficient and avoids recursion stack overhead.

Approach

Create a DP table dp where dp[i][j] stores the length of the longest palindromic subsequence between indices i and j.
Initialize all dp[i][i] to 1 (single characters are palindromes).
Fill the table for substrings of increasing length:
- If s[i] == s[j], set dp[i][j] = dp[i+1][j-1] + 2.
- Otherwise, set dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
To reconstruct the subsequence, start from dp[0][n-1] and trace back through the table, adding matching characters to the result.
Use examples to illustrate how the table is filled and how the subsequence is built.

Example Dry Run

For s = "agbdba", the DP table is filled as follows:

All diagonals are 1 (single characters).
For length 2, compare pairs and fill accordingly.
For longer substrings, use previously computed values.
The final answer is built by tracing back from dp[0][n-1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


def longest_palindromic_subsequence_dp(s: str) -> str:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2 if length > 2 else 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    # Reconstruct the subsequence
    res = []
    i, j = 0, n-1
    while i <= j:
        if s[i] == s[j]:
            if i == j:
                res.append(s[i])
            else:
                res.insert(len(res)//2, s[i])
                res.insert(len(res)//2+1, s[j])
            i += 1
            j -= 1
        elif dp[i+1][j] > dp[i][j-1]:
            i += 1
        else:
            j -= 1
    return ''.join(res)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution {
    public String longestPalindromicSubsequenceDP(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 + len - 1 < n; 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]);
                }
            }
        }
        // Reconstruct the subsequence
        StringBuilder left = new StringBuilder();
        StringBuilder right = new StringBuilder();
        int i = 0, j = n - 1;
        while (i <= j) {
            if (s.charAt(i) == s.charAt(j)) {
                if (i == j) {
                    left.append(s.charAt(i));
                } else {
                    left.append(s.charAt(i));
                    right.insert(0, s.charAt(j));
                }
                i++;
                j--;
            } else if (dp[i+1][j] > dp[i][j-1]) {
                i++;
            } else {
                j--;
            }
        }
        return left.append(right).toString();
    }
}

Complexity

⏰ Time complexity: O(N^2) — Filling the DP table and reconstructing the subsequence both take quadratic time.
🧺 Space complexity: O(N^2) — The DP table uses quadratic space.

Problem#

Examples#

Example 1#

Example 2#

Similar Problem#

Solution#

Method 1 - Naive#

Complexity#

Method 2 - Recursion#

Method 2 – Recursive Approach#

Intuition#

Approach#

Code#

Complexity#

Method 3 – Top Down DP (Memoization)#

Intuition#

Approach#

Code#

Complexity#

Method 4 – Bottom-Up DP (Tabulation)#

Intuition#

Approach#

Example Dry Run#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Similar Problem

Solution

Method 1 - Naive

Complexity

Method 2 - Recursion

Method 2 – Recursive Approach

Intuition

Approach

Code

Complexity

Method 3 – Top Down DP (Memoization)

Intuition

Approach

Code

Complexity

Method 4 – Bottom-Up DP (Tabulation)

Intuition

Approach

Example Dry Run

Code

Complexity