Hard

Longest Palindromic Subsequence II

LAB

Return the longest even-length palindromic subsequence where no two adjacent palindrome characters are equal.

EXAMPLES

Example 1

Input
{
  "s": "bbabab"
}

Output
4

FUNCTION SHAPE

s: string→int

SOLUTION NOTE

Track previous matched character. Return 0 when i == j to ensure even length only (exclude single middle char).

Reveal reference solution +

pythonREFERENCE

def longestPalindromeSubseq(self, s: str) -> int:
    @cache
    def dp(i, j, prev):
        if i >= j: return 0
        if s[i] == s[j] and s[i] != prev:
            return 2 + dp(i + 1, j - 1, s[i])
        return max(dp(i + 1, j, prev), dp(i, j - 1, prev))

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

TimeO(n² × 26)

SpaceO(n² × 26)

Open on LeetCode ↗