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

Unique Length-3 Palindromic Subsequences

Number: 2059

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta, Adobe

Problem Description

Given a string s, count the number of unique palindromic subsequences of length 3 that can be found as a subsequence in s. A palindromic sequence of length 3 has the form "a b a", where a and b are any characters. Even if the same sequence can be formed in multiple ways, it should only be counted once.

Key Insights

  • A valid palindrome of length 3 has the structure "a? a" where the first and last characters are the same.
  • For each character from 'a' to 'z', identify the first and last occurrence in the string.
  • Only if a character appears at least twice, there can be a valid palindrome with that character as both the first and last letter.
  • The middle character can be any distinct character that appears between the first and last occurrence of the outer character.
  • Using precomputation (like prefix sums or sets) optimizes the retrieval of unique mid characters between specific indices.

Space and Time Complexity

Time Complexity: O(n + 26*26) which is effectively O(n) since the alphabet size is constant. Space Complexity: O(n) if using auxiliary data structures such as prefix arrays or sets; otherwise O(1) additional space for constant size storage.

Solution

The approach involves these steps:

  1. Scan the string once to record the first and last positions for each letter.
  2. For each letter (from 'a' to 'z') that appears at least twice in the string, collect the unique characters (middle letters) that occur between its first and last positions.
  3. The count of unique length-3 palindromic subsequences contributed by that letter will be equal to the number of unique middle characters found.
  4. Sum all such counts to get the final answer.

Data Structures and Techniques:

  • Arrays or dictionaries to store first and last occurrence indices for each letter.
  • A set to accumulate unique middle characters between the two positions.
  • Iteration over the constant-size alphabet ensures a time complexity linear in the string length.

Code Solutions

Below are the code implementations in Python, JavaScript, C++, and Java.

# Python implementation
def countPalindromicSubsequence(s: str) -> int:
    # Initialize arrays to store the first and last occurrence for each letter
    firstOccurrence = [-1] * 26
    lastOccurrence = [-1] * 26

    # Record the first and last occurrence for each character in s
    for i, char in enumerate(s):
        index = ord(char) - ord('a')
        if firstOccurrence[index] == -1:
            firstOccurrence[index] = i
        lastOccurrence[index] = i

    uniqueCount = 0

    # For each letter as outer character
    for letter in range(26):
        # Only process if there is at least two occurrences
        if firstOccurrence[letter] != -1 and firstOccurrence[letter] < lastOccurrence[letter]:
            # Use a set to store unique middle letters that occur between the first and last occurrence
            middleLetters = set()
            for j in range(firstOccurrence[letter] + 1, lastOccurrence[letter]):
                middleLetters.add(s[j])
            uniqueCount += len(middleLetters)

    return uniqueCount

# Example usage:
print(countPalindromicSubsequence("aabca"))  # Expected output: 3
← Back to All Questions