Welcome to Subscribe On Youtube

1682. Longest Palindromic Subsequence II

Description

A subsequence of a string s is considered a good palindromic subsequence if:

  • It is a subsequence of s.
  • It is a palindrome (has the same value if reversed).
  • It has an even length.
  • No two consecutive characters are equal, except the two middle ones.

For example, if s = "abcabcabb", then "abba" is considered a good palindromic subsequence, while "bcb" (not even length) and "bbbb" (has equal consecutive characters) are not.

Given a string s, return the length of the longest good palindromic subsequence in s.

 

Example 1:

Input: s = "bbabab"
Output: 4
Explanation: The longest good palindromic subsequence of s is "baab".

Example 2:

Input: s = "dcbccacdb"
Output: 4
Explanation: The longest good palindromic subsequence of s is "dccd".

 

Constraints:

  • 1 <= s.length <= 250
  • s consists of lowercase English letters.

Solutions

Solution 1: Memorization Search

We design a function $dfs(i, j, x)$ to represent the length of the longest “good” palindrome subsequence ending with character $x$ in the index range $[i, j]$ of string $s$. The answer is $dfs(0, n - 1, 26)$.

The calculation process of the function $dfs(i, j, x)$ is as follows:

  • If $i >= j$, then $dfs(i, j, x) = 0$;
  • If $s[i] = s[j]$ and $s[i] \neq x$, then $dfs(i, j, x) = dfs(i + 1, j - 1, s[i]) + 2$;
  • If $s[i] \neq s[j]$, then $dfs(i, j, x) = max(dfs(i + 1, j, x), dfs(i, j - 1, x))$.

During the process, we can use memorization search to avoid repeated calculations.

The time complexity is $O(n^2 \times C)$. Where $n$ is the length of the string $s$, and $C$ is the size of the character set. In this problem, $C = 26$.

  • class Solution {
    private int[][][] f;
    private String s;

    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        this.s = s;
        f = new int[n][n][27];
        for (var a : f) {
            for (var b : a) {
                Arrays.fill(b, -1);
            }
        }
        return dfs(0, n - 1, 26);
    }

    private int dfs(int i, int j, int x) {
        if (i >= j) {
            return 0;
        }
        if (f[i][j][x] != -1) {
            return f[i][j][x];
        }
        int ans = 0;
        if (s.charAt(i) == s.charAt(j) && s.charAt(i) - 'a' != x) {
            ans = dfs(i + 1, j - 1, s.charAt(i) - 'a') + 2;
        } else {
            ans = Math.max(dfs(i + 1, j, x), dfs(i, j - 1, x));
        }
        f[i][j][x] = ans;
        return ans;
    }
}

  • class Solution {
public:
    int f[251][251][27];

    int longestPalindromeSubseq(string s) {
        int n = s.size();
        memset(f, -1, sizeof f);
        function<int(int, int, int)> dfs = [&](int i, int j, int x) -> int {
            if (i >= j) return 0;
            if (f[i][j][x] != -1) return f[i][j][x];
            int ans = 0;
            if (s[i] == s[j] && s[i] - 'a' != x)
                ans = dfs(i + 1, j - 1, s[i] - 'a') + 2;
            else
                ans = max(dfs(i + 1, j, x), dfs(i, j - 1, x));
            f[i][j][x] = ans;
            return ans;
        };
        return dfs(0, n - 1, 26);
    }
};

  • '''
Create a 3D array `dp` of size `n * n * 26`, where `dp[i][j][k]` represents the length of the longest palindromic subsequence from index `i` to index `j` where the outmost letter is the `k`-th letter (0-indexed).
'''
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        length = len(s)
        dp = [[ [0] * 26 for _ in range(length) ] for _ in range(length)]
        for i in range(length - 2, -1, -1):
            for j in range(i + 1, length):
                for k in range(26):
                    c = chr(ord('a') + k)
                    if s[i] != c:
                        dp[i][j][k] = dp[i + 1][j][k]
                    elif s[j] != c:
                        dp[i][j][k] = dp[i][j - 1][k]
                    else:
                        prevLength = max(dp[i + 1][j - 1][m] for m in range(26) if m != k)
                        dp[i][j][k] = prevLength + 2
        maxLength = 0
        for k in range(26):
            maxLength = max(maxLength, dp[0][length - 1][k])
        return maxLength

############

'''
Using @cache and cache_clear() together allows for both optimizing recursive functions and managing memory usage effectively by caching results for repeated calls and clearing the cache when it's no longer needed.

The cache_clear() method clears the cache of all stored results for the dfs function. This is particularly useful for resetting the state or when you no longer need the cached results, allowing the garbage collector to reclaim the memory.
'''
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def dfs(i, j, x):
            if i >= j: # i==j, then it's an odd one, not valid
                return 0
            if s[i] == s[j] and s[i] != x:
                return dfs(i + 1, j - 1, s[i]) + 2
            return max(dfs(i + 1, j, x), dfs(i, j - 1, x))

        ans = dfs(0, len(s) - 1, '')
        dfs.cache_clear() # note: good practise
        return ans


  • func longestPalindromeSubseq(s string) int {
	n := len(s)
	f := make([][][]int, n)
	for i := range f {
		f[i] = make([][]int, n)
		for j := range f[i] {
			f[i][j] = make([]int, 27)
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	var dfs func(i, j, x int) int
	dfs = func(i, j, x int) int {
		if i >= j {
			return 0
		}
		if f[i][j][x] != -1 {
			return f[i][j][x]
		}
		ans := 0
		if s[i] == s[j] && int(s[i]-'a') != x {
			ans = dfs(i+1, j-1, int(s[i]-'a')) + 2
		} else {
			ans = max(dfs(i+1, j, x), dfs(i, j-1, x))
		}
		f[i][j][x] = ans
		return ans
	}
	return dfs(0, n-1, 26)
}

All Problems

All Solutions