Problem

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 _thelength of the longest good palindromic subsequence in _s.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Method 1 – Dynamic Programming with State Compression

Intuition

The key idea is to use dynamic programming to find the longest even-length palindromic subsequence with no consecutive equal characters (except the middle two). We try all possible pairs of characters for the ends and recursively solve for the inner substring, ensuring the constraints are met.

Approach

  1. Use a 3D DP array: dp[l][r][c] where l and r are the current left and right indices, and c is the character at the ends (0-25 for ‘a’-‘z’).
  2. For each pair of indices (l, r), try all possible characters for the ends.
  3. If s[l] == s[r] == ch and the substring between them can form a good palindromic subsequence, update the answer.
  4. Ensure that no two consecutive characters are equal except the middle two.
  5. Return the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(26, 0)));
        int ans = 0;
        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l + len - 1 < n; ++l) {
                int r = l + len - 1;
                for (int ch = 0; ch < 26; ++ch) {
                    if (s[l] - 'a' == ch && s[r] - 'a' == ch) {
                        if (len == 2) dp[l][r][ch] = 2;
                        else {
                            for (int mid = 0; mid < 26; ++mid) {
                                if (mid != ch) dp[l][r][ch] = max(dp[l][r][ch], dp[l+1][r-1][mid] + 2);
                            }
                        }
                    }
                    ans = max(ans, dp[l][r][ch]);
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, 26)
        }
    }
    ans := 0
    for l := 0; l < n; l++ {
        for ch := 0; ch < 26; ch++ {
            if int(s[l]-'a') == ch {
                dp[l][l][ch] = 0
            }
        }
    }
    for length := 2; length <= n; length++ {
        for l := 0; l+length-1 < n; l++ {
            r := l + length - 1
            for ch := 0; ch < 26; ch++ {
                if int(s[l]-'a') == ch && int(s[r]-'a') == ch {
                    if length == 2 {
                        dp[l][r][ch] = 2
                    } else {
                        for mid := 0; mid < 26; mid++ {
                            if mid != ch {
                                if dp[l+1][r-1][mid]+2 > dp[l][r][ch] {
                                    dp[l][r][ch] = dp[l+1][r-1][mid] + 2
                                }
                            }
                        }
                    }
                }
                if dp[l][r][ch] > ans {
                    ans = dp[l][r][ch]
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][][] dp = new int[n][n][26];
        int ans = 0;
        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l + len - 1 < n; ++l) {
                int r = l + len - 1;
                for (int ch = 0; ch < 26; ++ch) {
                    if (s.charAt(l) - 'a' == ch && s.charAt(r) - 'a' == ch) {
                        if (len == 2) dp[l][r][ch] = 2;
                        else {
                            for (int mid = 0; mid < 26; ++mid) {
                                if (mid != ch) dp[l][r][ch] = Math.max(dp[l][r][ch], dp[l+1][r-1][mid] + 2);
                            }
                        }
                    }
                    ans = Math.max(ans, dp[l][r][ch]);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val dp = Array(n) { Array(n) { IntArray(26) } }
        var ans = 0
        for (len in 2..n) {
            for (l in 0..n-len) {
                val r = l + len - 1
                for (ch in 0..25) {
                    if (s[l] - 'a' == ch && s[r] - 'a' == ch) {
                        if (len == 2) dp[l][r][ch] = 2
                        else {
                            for (mid in 0..25) {
                                if (mid != ch) dp[l][r][ch] = maxOf(dp[l][r][ch], dp[l+1][r-1][mid] + 2)
                            }
                        }
                    }
                    ans = maxOf(ans, dp[l][r][ch])
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[[0]*26 for _ in range(n)] for _ in range(n)]
        ans = 0
        for length in range(2, n+1):
            for l in range(n-length+1):
                r = l + length - 1
                for ch in range(26):
                    if ord(s[l])-ord('a') == ch and ord(s[r])-ord('a') == ch:
                        if length == 2:
                            dp[l][r][ch] = 2
                        else:
                            for mid in range(26):
                                if mid != ch:
                                    dp[l][r][ch] = max(dp[l][r][ch], dp[l+1][r-1][mid]+2)
                    ans = max(ans, dp[l][r][ch])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn longest_palindrome_subseq(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut dp = vec![vec![vec![0; 26]; n]; n];
        let mut ans = 0;
        for len in 2..=n {
            for l in 0..=n-len {
                let r = l + len - 1;
                for ch in 0..26 {
                    if s[l] - b'a' == ch as u8 && s[r] - b'a' == ch as u8 {
                        if len == 2 {
                            dp[l][r][ch] = 2;
                        } else {
                            for mid in 0..26 {
                                if mid != ch {
                                    dp[l][r][ch] = dp[l][r][ch].max(dp[l+1][r-1][mid] + 2);
                                }
                            }
                        }
                    }
                    ans = ans.max(dp[l][r][ch]);
                }
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    longestPalindromeSubseq(s: string): number {
        const n = s.length;
        const dp = Array.from({length: n}, () => Array.from({length: n}, () => Array(26).fill(0)));
        let ans = 0;
        for (let len = 2; len <= n; ++len) {
            for (let l = 0; l + len - 1 < n; ++l) {
                const r = l + len - 1;
                for (let ch = 0; ch < 26; ++ch) {
                    if (s.charCodeAt(l) - 97 === ch && s.charCodeAt(r) - 97 === ch) {
                        if (len === 2) dp[l][r][ch] = 2;
                        else {
                            for (let mid = 0; mid < 26; ++mid) {
                                if (mid !== ch) dp[l][r][ch] = Math.max(dp[l][r][ch], dp[l+1][r-1][mid] + 2);
                            }
                        }
                    }
                    ans = Math.max(ans, dp[l][r][ch]);
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3 * 26), as we check all substrings and all character pairs for each substring.
  • 🧺 Space complexity: O(n^2 * 26), for the DP table storing results for all substring pairs and characters.