Medium

Longest Palindromic Subsequence

LAB

Return the length of the longest subsequence of s that is a palindrome.

EXAMPLES

Example 1

Input
{
  "s": "bbbab"
}

Output
4

FUNCTION SHAPE

s: string→int

SOLUTION NOTE

Key insight: Longest Palindromic Subsequence = LCS of string with its reverse.

Reveal reference solution +

pythonREFERENCE

def longestPalindromeSubseq(self, s: str) -> int:
    # LPS(s) = LCS(s, reverse(s))
    t = s[::-1]

    @cache
    def dp(i, j):
        if i < 0 or j < 0: return 0
        if s[i] == t[j]:
            return 1 + dp(i-1, j-1)
        return max(dp(i-1, j), dp(i, j-1))

    return dp(len(s)-1, len(s)-1)

TimeO(n²)

SpaceO(n²)

Open on LeetCode ↗