We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Palindromic Subsequence II

Number: 1822

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a lowercase string s, find the length of the longest subsequence which is a palindrome with even length and satisfies an additional rule: aside from the very middle pair, every two consecutive characters in the subsequence must be different. In other words, the subsequence (which is “good”) must be a palindrome of even length, and if you look at every adjacent pair of characters it must be that they differ, except for the two characters in the center (which come from the same pair).

For example, if s = "bbabab", one answer is "baab" (length 4). Note that “bcb” is not acceptable because its length is odd, and “bbbb” is not acceptable because (apart from the middle pair) adjacent characters are equal.

Key Insights

  • We want an even-length palindromic subsequence that is “good” – that is, its left half (when read normally) should have no adjacent equal letters; the right half will be its mirror (and its first character may equal the last character of the left half).
  • We can think of constructing the palindrome in pairs: each pair contributes 2 characters. When choosing a new pair (with both characters equal), the left (first half) character must be different from the previous pair’s left character.
  • A recursive formulation (DP) can be designed over an interval [l, r] of the original string with an extra parameter representing the last chosen left character (or a sentinel if none was chosen so far). For each character c (from ‘a’ to ‘z’) different from the previous left character, we want to check whether c appears at least twice in the current segment. If yes, we can “pair up” its leftmost and rightmost occurrences and add 2 plus the optimal answer from the “middle” segment, while updating the last chosen left character to c.
  • To speed up these searches, precomputing for every character the ordered list of indices where it appears allows efficient queries (using binary search) for the first occurrence ≥ l and last occurrence ≤ r.
  • Finally, the answer is given by dp(0, n – 1, sentinel) where sentinel indicates that no left character has yet been chosen.

Space and Time Complexity

Time Complexity: O(n² * 26 * log(n))
Space Complexity: O(n² * 27) for memoization plus O(n) for precomputed index lists

Solution

We use dynamic programming with recursion and memoization. The state is defined as dp(l, r, prev) where l and r denote the current substring boundaries and prev is the last chosen left-half character (or a special sentinel value such as -1 if none is chosen). For each character c from 'a' to 'z' (skipping if c equals prev) we check if there is at least one occurrence in s[l..r] and, crucially, if there is a pair (i, j) (with i < j) such that s[i] = s[j] = c. Using our precomputed lists for each character, we can quickly obtain the leftmost index and rightmost index of c in the interval. If such a pair exists then one candidate answer is 2 (for the pair) plus dp(i+1, j-1, c) where the new “prev” becomes c (ensuring that the next added pair’s left letter is different). We take the maximum candidate across all characters and memoize the result.

The extra twist of “no two consecutive characters equal, except for the two middle ones” is managed by the fact that if we add a new pair (with left character c), we only allow that when c is not equal to the previously chosen left character.

Code Solutions

# Python solution with detailed comments
from bisect import bisect_left, bisect_right
from functools import lru_cache
from collections import defaultdict

def longestGoodPalindromicSubsequence(s: str) -> int:
    n = len(s)
    # Precompute the indices for each character in the string
    char_positions = defaultdict(list)
    for index, ch in enumerate(s):
        char_positions[ch].append(index)
    
    # dp(l, r, prev) returns the maximum length of a good palindromic subsequence
    # that can be built from s[l...r] given that the last chosen left-half character is "prev"
    # If no character has been chosen yet, prev is set to '#' (or any symbol not in s).
    @lru_cache(maxsize=None)
    def dp(l: int, r: int, prev: str) -> int:
        # If the interval is empty or invalid, return 0
        if l >= r:
            return 0
        
        best = 0
        # iterate over all lowercase letters
        for ch in "abcdefghijklmnopqrstuvwxyz":
            # We cannot pick the same letter consecutively in the left half.
            if ch == prev:
                continue
            # Get the list of indices for current character ch
            positions = char_positions[ch]
            # Find the leftmost occurrence in [l, r]
            li = bisect_left(positions, l)
            if li == len(positions) or positions[li] > r:
                continue  # ch does not appear in the [l, r] interval.
            # Find the rightmost occurrence in [l, r]
            ri = bisect_right(positions, r) - 1
            # Ensure that we have two distinct positions for ch in [l, r]
            if positions[li] < positions[ri]:
                candidate = 2 + dp(positions[li] + 1, positions[ri] - 1, ch)
                best = max(best, candidate)
        return best

    # Use '#' as sentinel for prev since s consists of a-z
    return dp(0, n - 1, '#')

# Example usage:
#print(longestGoodPalindromicSubsequence("bbabab"))  # Output: 4
← Back to All Questions