Editorial for Longest Palindromic Subsequence

Approach

Let $dp[l][r]$ be the length of the longest palindromic subsequence inside the substring $s_l, s_{l+1}, \ldots, s_r$.

If $s_l = s_r$, then these two characters can be used as the matching ends of a palindrome, so $dp[l][r] = dp[l+1][r-1] + 2$. Otherwise, at least one of the two ends is not used, so $dp[l][r] = \max(dp[l+1][r], dp[l][r-1])$.

Process $l$ from right to left and $r$ from left to right. The implementation below stores only one row of the dynamic program, keeping the old value of $dp[l+1][r-1]$ in a variable before it is overwritten. The time complexity is $O(n^2)$.

Solution (Python)

import sys


def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    dp = [0] * n

    for i in range(n - 1, -1, -1):
        previous_diagonal = 0
        dp[i] = 1
        current = s[i]

        for j in range(i + 1, n):
            old = dp[j]
            if current == s[j]:
                dp[j] = previous_diagonal + 2
            elif dp[j - 1] > dp[j]:
                dp[j] = dp[j - 1]
            previous_diagonal = old

    return dp[-1]


def main() -> None:
    data = sys.stdin.read().split()
    n = int(data[0])
    s = data[1]
    assert len(s) == n
    print(longest_palindromic_subsequence(s))


if __name__ == "__main__":
    main()