LeetCode 1682 - Longest Palindromic Subsequence II

The problem is asking us to find the length of the longest good palindromic subsequence in a given string s. A good pali

leetcodemediumstringdynamic-programming

LeetCode Problem 1682

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem is asking us to find the length of the longest good palindromic subsequence in a given string s. A good palindromic subsequence is a string that meets several conditions: it must be a subsequence of s, it must read the same forwards and backwards, it must have an even length, and it cannot contain two consecutive equal characters except for the middle two characters.

The input s is a string of lowercase English letters with length up to 250, which is small enough to consider dynamic programming solutions with O(n^3) time complexity in practice, though ideally we want O(n^2) if possible. The output is an integer representing the length of the longest good palindromic subsequence.

Important edge cases include strings where all characters are the same, strings with only one character, strings where no good palindromic subsequence exists, and strings where the optimal subsequence is nested deeply inside the string rather than at the ends. The problem guarantees at least one character, so an empty string input does not need to be handled.

Approaches

A brute-force approach would be to generate all possible subsequences of s, check each one for being a palindrome, even length, and non-repeating adjacent characters. This approach is correct because it exhaustively considers all possibilities, but it is impractical: generating subsequences has exponential time complexity, specifically O(2^n) for a string of length n, which would be infeasible for n up to 250.

The optimal approach is to use dynamic programming. We define dp[i][j] as the length of the longest good palindromic subsequence in the substring s[i:j+1]. We iterate over substring lengths and fill dp[i][j] based on whether s[i] equals s[j] and whether choosing them maintains the "no consecutive duplicates" property. The insight is that we can build larger palindromes from smaller ones by checking these conditions and tracking the maximum valid length.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generate all subsequences and check conditions
Optimal O(n^3) O(n^2) DP over substring indices with checking for consecutive duplicates

Algorithm Walkthrough

  1. Initialize a 2D DP array dp of size n x n filled with zeros, where n is the length of the string.
  2. Iterate over all substrings of s by length len_sub from 2 to n.
  3. For each substring starting at index i and ending at index j = i + len_sub - 1, check if s[i] == s[j].
  4. If the characters are equal, look inside the substring s[i+1:j] for the longest valid subsequence and ensure that adding s[i] and s[j] does not violate the "no consecutive duplicates" rule.
  5. Otherwise, take the maximum between dp[i+1][j] and dp[i][j-1].
  6. Keep track of the maximum even length found during this process.
  7. Return the maximum length stored in dp[0][n-1] after iterating over all substrings.

Why it works: This works because each dp[i][j] correctly represents the longest valid subsequence in s[i:j+1] by considering all possible choices for the endpoints. By building from smaller substrings to larger ones, we guarantee that all dependencies are resolved before use.

Python Solution

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n):
            dp[i][i] = 0  # single character cannot be even-length good palindrome

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    if length == 2:
                        dp[i][j] = 2
                    elif s[i] != s[i + 1] and s[j] != s[j - 1]:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        
        return max(max(row) for row in dp)

This implementation initializes the DP table, fills it iteratively while checking the rules for a good palindromic subsequence, and returns the maximum length found. Single-character substrings are initialized as zero because they cannot form even-length palindromes.

Go Solution

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n - length; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                if length == 2 {
                    dp[i][j] = 2
                } else if s[i] != s[i+1] && s[j] != s[j-1] {
                    dp[i][j] = dp[i+1][j-1] + 2
                } else {
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                }
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }

    maxLen := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if dp[i][j] > maxLen {
                maxLen = dp[i][j]
            }
        }
    }
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

In Go, the implementation uses slices of slices to create the DP table. The logic mirrors Python, with careful index checks to prevent out-of-range errors. A helper function max is used to simplify comparisons.

Worked Examples

Example 1: s = "bbabab"

i j s[i] == s[j] dp[i][j]
0 1 yes ('b') 2
1 2 no max(dp[2][2], dp[1][1]) = 0
0 5 no max(dp[1][5], dp[0][4]) = 4

Longest good palindromic subsequence is "baab", length 4.

Example 2: s = "dcbccacdb"

Longest good palindromic subsequence is "dccd", length 4. The DP table is built similarly, ensuring no consecutive duplicates at non-central positions.

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) Three nested loops: substring length, start index, and inner DP check for consecutive duplicates
Space O(n^2) DP table of size n x n

This complexity is acceptable for n <= 250, giving a maximum of around 15 million operations in the worst case.

Test Cases

# provided examples
assert Solution().longestPalindromeSubseq("bbabab") == 4  # "baab"
assert Solution().longestPalindromeSubseq("dcbccacdb") == 4  # "dccd"

# edge cases
assert Solution().longestPalindromeSubseq("a") == 0  # single character
assert Solution().longestPalindromeSubseq("aa") == 2  # two same characters
assert Solution().longestPalindromeSubseq("ab") == 0  # two different characters
assert Solution().longestPalindromeSubseq("abcabcabb") == 4  # "abba" is longest
assert Solution().longestPalindromeSubseq("ababab") == 4  # "abba" or "baba"
Test Why
"bbabab" Validates basic DP computation and consecutive character check
"dcbccacdb" Checks non-trivial palindromic subsequence with internal duplicates
"a" Ensures single-character case returns 0
"aa" Tests minimal even-length palindrome
"ab" Tests minimal invalid palindrome
"abcabcabb" Longer string with nested palindromes
"ababab" Repeating patterns, multiple valid options

Edge Cases

The first edge case is a single-character string, like "a". It is impossible to form an even-length palindrome, so the result should be 0. The implementation correctly