Editorial for Longest Palindromic Subsequence

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

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

If $s_l = s_r$ ~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$ ~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$ ~l~ from right to left and $r$ ~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]$ ~dp[l+1][r-1]~ in a variable before it is overwritten. The time complexity is $O(n^2)$ ~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()

Comments

There are no comments at the moment.