Problem statement

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

Solution

One way to solve this problem is to use dynamic programming with states dp(l, r, prev), where [l, r] is interval we are working with and prev is previous symbol we take.

  1. if s[l] == s[r] != prev, it means that we can take s[l] and s[r] to extend our palindrome.
  2. in the opposite case, one of the symbols s[l] or s[r] will not be taken, so return maximum among these two possibilities.

Complexity

It is O(n^2 * s), where s is the size of alphabet.

Code

class Solution:
    def longestPalindromeSubseq(self, s):
        @lru_cache(None)
        def dp(l, r, prev):
            if l >= r: return 0
            if s[l] == s[r] != prev: return 2 + dp(l + 1, r - 1, s[l])
            return max(dp(l + 1, r, prev), dp(l, r - 1, prev))
        
        ans = dp(0, len(s) - 1, '')
        dp.cache_clear()
        return ans

Remark

To avoid TLE for lru_cache we can use dp.cache_clear(). There is also O(n^2) time complexity solution without factor s.