Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1682.html

Level

Medium

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.

Solution

Use dynamic programming. Let n be the length of s. 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). For each pair of (i, j) where i < j, loop over k. Let c be the k-th letter. If s.charAt(i) != c, then dp[i][j][k] = dp[i + 1][j][k]. If s.charAt(j) != c, then dp[i][j][k] = dp[i][j - 1][k]. Otherwise, loop over m from 0 to 25 and calculate the maximum previous length as prevLength = max{dp[i + 1][j - 1][m]} among the values of m where m != k. Then dp[i][j][k] = prevLength + 2.

After the values of dp are calculated, loop over k from 0 to 25 to obtain the maximum among dp[0][n - 1][k]. Finally, return the maximum.

Code

  • class Solution {
        public int longestPalindromeSubseq(String s) {
            int length = s.length();
            int[][][] dp = new int[length][length][26];
            for (int i = length - 2; i >= 0; i--) {
                for (int j = i + 1; j < length; j++) {
                    for (int k = 0; k < 26; k++) {
                        char c = (char) ('a' + k);
                        if (s.charAt(i) != c)
                            dp[i][j][k] = dp[i + 1][j][k];
                        else if (s.charAt(j) != c)
                            dp[i][j][k] = dp[i][j - 1][k];
                        else {
                            int prevLength = 0;
                            for (int m = 0; m < 26; m++) {
                                if (m != k) // here is to satisfy 'No two consecutive characters are equal, except the two middle ones.'
                                    prevLength = Math.max(prevLength, dp[i + 1][j - 1][m]);
                            }
                            dp[i][j][k] = prevLength + 2;
                        }
                    }
                }
            }
            int maxLength = 0;
            for (int k = 0; k < 26; k++)
                maxLength = Math.max(maxLength, dp[0][length - 1][k]);
            return maxLength;
        }
    }
    
    
    ############
    
    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);
        }
    };
    
  • class Solution:
        def longestPalindromeSubseq(self, s: str) -> int:
            length = len(s)
            dp = [[[0 for _ in range(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 = 0
                            for m in range(26):
                                if m != k:
                                    prevLength = max(prevLength, dp[i + 1][j - 1][m])
                            dp[i][j][k] = prevLength + 2
            maxLength = 0
            for k in range(26):
                maxLength = max(maxLength, dp[0][length - 1][k])
            return maxLength
    
    ############
    
    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()
            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)
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions