516. Longest Palindromic Subsequence.md

516. Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/

Thinking by DP. Let lps(i, j) be the longest palindromic subsequence of the substring s[i..j], lps(i, j) be the length of |lps(i, j)|. We need to know |lps(0, |s| - 1)|

Lemma 1: If s[i] == s[j], then lps(i, j) must contains s[i] and s[j].

Proof by contradiction: assume t = lps(i, j) does not contains s[i] and s[j], you can attach them to the two ends of t. The resulting string t' is also a subsequence of s[i..j] and is also a palindrom. So t' is the longest palindromic subsequence, which is longer than t. Q.E.D

Lemma 2: If s[i] != s[j] and s[i] is in lps(i, j), then s[j] must NOT be in it.

Thus, we have the reccurence relation as below:

|lps(i, j)|  | s[i] == s[j] = 2 + |lps(i + 1, j - 1)| // by lemma 1
             | otherwise    = max(|lps(i, j - 1)|,    // by lemma 2
                                  |lps(i + 1, j)|)    // s[i] not in lps(i, j)

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def lps(i, j):
            if i > j:
                return 0
            if i == j:
                return 1
            if s[i] == s[j]:
                return 2 + lps(i + 1, j - 1)
            return max(lps(i + 1, j), lps(i, j - 1))

        return lps(0, len(s) - 1)