LeetCode 1682. Longest Palindromic Subsequence II Solution in Java, C++, Python & Go | Explanation + Code

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] ≠ x, then dfs(i, j, x) = dfs(i + 1, j - 1, s[i]) + 2;
• If s[i] ≠ 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² × C). Where n is the length of the string s, and C is the size of the character set. In this problem, C = 26.

PythonJavaC++Go

class Solution: def longestPalindromeSubseq(self, s: str) -> int: @cache def dfs(i, j, x): if i >= j: 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() return ans(code-box)

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; } }(code-box)

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); } };(code-box)

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) }(code-box)