Longest Palindromic Subsequence | Leetcode 516

Given a string s, find the length of the longest palindromic subsequence in s. A subsequence keeps relative order but is not required to be contiguous.

A standard reduction is to compute the Longest Common Subsequence (LCS) between s and its reverse rev(s). The LCS length equals the Longest Palindromic Subsequence length.

Here’s the [Problem Link] to begin with.

Example 1

Input:  s = "bbbab"
Output: 4
Explanation: One LPS is "bbbb" with length 4.

Example 2

Input:  s = "cbbd"
Output: 2
Explanation: One LPS is "bb" with length 2.

Intuition and Approach

1. Convert LPS to LCS by setting s1 = s and s2 = reverse(s).
2. Compute LCS length of s1 and s2 using any LCS technique.
3. The resulting LCS length is the answer to LPS.

Below are three implementations that follow this plan.

Memoization

Intuition and Approach

Top down recursion with caching on indices (ind1, ind2) over s1 and s2.
Use 1-based indexing in the DP table for clean base cases. Matching characters add 1 and move diagonally. Otherwise, take the maximum of skipping one character from either string.

Code Implementation

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]

        def solve(ind1: int, ind2: int) -> int:
            if ind1 == 0 or ind2 == 0:
                return 0
            if dp[ind1][ind2] != -1:
                return dp[ind1][ind2]
            if text1[ind1 - 1] == text2[ind2 - 1]:
                dp[ind1][ind2] = 1 + solve(ind1 - 1, ind2 - 1)
            else:
                dp[ind1][ind2] = 0 + max(solve(ind1 - 1, ind2), solve(ind1, ind2 - 1))
            return dp[ind1][ind2]

        return solve(n, m)

    def longestPalindromeSubseq(self, s: str) -> int:
        s1 = s
        s2 = s[::-1]
        return self.longestCommonSubsequence(s1, s2)

Code explanation

• solve(i, j) returns LCS length for text1[:i] and text2[:j].
• Base case when either prefix is empty returns 0.
• On a match, move diagonally and add 1.
• On a mismatch, keep the best by moving up or left.
• longestPalindromeSubseq computes LCS(s, reverse(s)).

Time and Space Complexity

• Precise: O(n*m) states with O(1) work each after memoization, total O(n*m). Recursion stack up to O(n + m). DP table O(n*m) space.
• Simplified: O(n*m) time, O(n*m) space.

Conclusion

Memoization turns the exponential recursion into a polynomial solution while keeping code close to the mathematical recurrence.

Tabulation

Intuition and Approach

Bottom up LCS over s1 and s2 = reverse(s). Build a (n+1) x (m+1) table where row 0 and column 0 are zeros. Fill row by row using standard LCS transitions.

Code Implementation

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
        for ind2 in range(0, m + 1):
            dp[0][ind2] = 0
        for ind1 in range(0, n + 1):
            dp[ind1][0] = 0
        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                if text1[ind1 - 1] == text2[ind2 - 1]:
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
                else:
                    dp[ind1][ind2] = 0 + max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
        return dp[n][m]

    def longestPalindromeSubseq(self, s: str) -> int:
        s1 = s
        s2 = s[::-1]
        return self.longestCommonSubsequence(s1, s2)

Code explanation

• Initializes first row and column to 0 for empty prefixes.
• Fills each cell using match or max of neighbors rule.
• dp[n][m] is the LCS length, which equals the LPS length.

Time and Space Complexity

• Precise: build n*m table cells in O(1) each, so O(n*m) time and O(n*m) space.
• Simplified: O(n*m) time and space.

Conclusion

Tabulation is iterative, avoids recursion, and is a good base for reconstructing the subsequence if needed.

Tabulation (Space Optimize)

Intuition and Approach

LCS recurrence uses only the previous row and current row. Keep two arrays and roll them as you iterate rows. Apply this to s1 and reverse(s2) for LPS.

Code Implementation

class SolutionSpaceOptimized:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        prev = [0] * (m + 1)

        for ind1 in range(1, n + 1):
            cur = [0] * (m + 1)
            for ind2 in range(1, m + 1):
                if text1[ind1 - 1] == text2[ind2 - 1]:
                    cur[ind2] = 1 + prev[ind2 - 1]
                else:
                    cur[ind2] = 0 + max(prev[ind2], cur[ind2 - 1])
            prev = cur

        return prev[m]

    def longestPalindromeSubseq(self, s: str) -> int:
        s1 = s
        s2 = s[::-1]
        return self.longestCommonSubsequence(s1, s2)

Code explanation

• prev represents the previous DP row and cur the current row.
• Update cur[j] from prev[j-1], prev[j], and cur[j-1].
• After finishing a row, assign prev = cur.
• The final LCS length is prev[m], which is the LPS length.

Time and Space Complexity

• Precise: O(n*m) time. Arrays of size m+1 give O(m) extra space.
• Simplified: O(n*m) time and O(min(n, m)) space if you choose the shorter string as columns.

Conclusion

Space optimization preserves time optimality and significantly reduces memory, which is useful for long strings when only the length is required.

Final takeaway

• Longest Palindromic Subsequence reduces cleanly to LCS between s and reverse(s).
• Memoization, tabulation, and space optimized tabulation all run in O(n*m) time, with differing space costs.
• Choose the space optimized version when memory matters and only the length is needed.
• If you also want to print one LPS, use the full table so you can backtrack, similar to printing an LCS.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.