1930. Unique Length 3 Palindromic Subsequences - Explanation

1. Brute Force (Recursion)

Intuition

A length-3 palindrome has the form aba where the first and third characters are the same. We can use recursion to generate all subsequences of length 3 and check which ones are palindromes. This explores all possible combinations by either including or excluding each character.

Algorithm

Use a set to store unique palindromic subsequences.
Define a recursive function rec(i, cur) where i is the current index and cur is the current subsequence being built.
If cur has length 3:
- Check if it's a palindrome (first and last characters match).
- If yes, add it to the set.
- Return.
If i reaches the end of the string, return.
Make two recursive calls: skip the current character, or include it.
Start with rec(0, "") and return the size of the set.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = set()

        def rec(i, cur):
            if len(cur) == 3:
                if cur[0] == cur[2]:
                    res.add(cur)
                return
            if i == len(s):
                return
            rec(i + 1, cur)
            rec(i + 1, cur + s[i])

        rec(0, "")
        return len(res)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n + m)$

Where $n$ is the length of the string $s$ and $m$ is the number of unique three length pallindromic subsequences (26 * 26 = 676).

2. Brute Force

Intuition

Instead of generating all subsequences recursively, we can use three nested loops to pick positions for the three characters. For indices i < j < k, we check if s[i] == s[k] to form a palindrome. Using a set ensures we count each unique palindrome only once.

Algorithm

Use a set to store unique palindromic subsequences.
For each index i from 0 to n-3:
- For each index j from i+1 to n-2:
  - For each index k from j+1 to n-1:
    - If s[i] == s[k], add the string s[i] + s[j] + s[k] to the set.
Return the size of the set.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = set()

        for i in range(len(s) - 2):
            for j in range(i + 1, len(s) - 1):
                for k in range(j + 1, len(s)):
                    if s[i] != s[k]:
                        continue
                    res.add(s[i] + s[j] + s[k])
        return len(res)

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the number of unique three length pallindromic subsequences (26 * 26 = 676).

3. Sequential Matching for Each Palindrome

Intuition

Since we only have 26 lowercase letters, there are at most 26 * 26 = 676 possible palindromes of length 3 (26 choices for the end characters, 26 for the middle). We can check each potential palindrome by scanning the string once to see if it exists as a subsequence.

Algorithm

Initialize res = 0.
For each possible end character (a to z):
- For each possible middle character (a to z):
  - Form the palindrome string ends + mid + ends.
  - Scan through the input string trying to match this 3-character sequence in order.
  - If matched, increment res.
Return res.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0
        for ends in range(ord('a'), ord('z') + 1):
            for mid in range(ord('a'), ord('z') + 1):
                seq = chr(ends) + chr(mid) + chr(ends)
                idx, found = 0, 0
                for c in s:
                    if seq[idx] == c:
                        idx += 1
                        if idx == 3:
                            found = 1
                            break
                res += found
        return res

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$

Where $n$ is the length of the string $s$ and $m$ is the number of unique three length pallindromic subsequences (26 * 26 = 676).

4. Iterate On Middle Characters

Intuition

Instead of checking all possible palindromes, we can iterate through the string and treat each position as a potential middle character. For each middle position, we need to know which characters appear both before and after it. A palindrome exists if the same character appears on both sides.

Algorithm

Count the frequency of each character in the string (this represents characters to the right).
Maintain a set of characters seen so far (characters to the left).
Use a set to store unique palindromes found.
For each character s[i] in the string:
- Decrement its count in the right frequency array.
- For each letter that appears in both left set and right array, add (s[i], letter) to the result set (representing the palindrome letter + s[i] + letter).
- Add s[i] to the left set.
Return the size of the result set.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = set()
        left = set()
        right = collections.Counter(s)

        for i in range(len(s)):
            right[s[i]] -= 1
            if right[s[i]] == 0:
                right.pop(s[i])

            for j in range(26):
                c = chr(ord('a') + j)
                if c in left and c in right:
                    res.add((s[i], c))
            left.add(s[i])

        return len(res)

Time & Space Complexity

Time complexity: $O(26 * n)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the number of unique three length pallindromic subsequences (26 * 26 = 676).

5. Prefix Count

Intuition

We can precompute prefix counts for each character, allowing us to quickly determine how many of each character appear in any substring. For each possible end character, we find its first and last occurrence, then count distinct middle characters between them using prefix sums.

Algorithm

Build a prefix count array where prefix[i][c] = count of character c in s[0..i-1].
Track the first and last index of each character.
For each character that appears at least twice (has different first and last indices):
- Let l = firstIndex and r = lastIndex.
- For each possible middle character, check if prefix[r][mid] - prefix[l+1][mid] > 0.
- If yes, that palindrome exists; increment the result.
Return the total count.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        n = len(s)
        prefix = [[0] * 26 for _ in range(n + 1)]
        firstIndex = [-1] * 26
        lastIndex = [-1] * 26

        for i in range(n):
            j = ord(s[i]) - ord('a')
            if firstIndex[j] == -1:
                firstIndex[j] = i
            lastIndex[j] = i
            prefix[i + 1] = prefix[i][:]
            prefix[i + 1][j] += 1

        res = 0
        for ends in range(26):
            if firstIndex[ends] == -1 or firstIndex[ends] == lastIndex[ends]:
                continue
            l, r = firstIndex[ends], lastIndex[ends]
            for mid in range(26):
                if prefix[r][mid] - prefix[l + 1][mid] > 0:
                    res += 1
        return res

Time & Space Complexity

Time complexity: $O(26 * n)$
Space complexity: $O(26 * n)$

6. First And Last Index

Intuition

For a length-3 palindrome with character c at both ends, we need at least two occurrences of c. The palindrome can use any character between the first and last occurrence of c as the middle. By finding the first and last index of each character, we can count the distinct characters in between.

Algorithm

For each character c from 'a' to 'z':
- Find the first index l and last index r of c in the string.
- If c doesn't appear twice, skip it.
- Collect all distinct characters between indices l+1 and r-1 into a set.
- Add the size of this set to the result.
Return the total result.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0

        for i in range(26):
            c = chr(ord('a') + i)
            l, r = s.find(c), s.rfind(c)
            if l == -1 or l == r:
                continue

            mids = set()
            for j in range(l + 1, r):
                mids.add(s[j])
            res += len(mids)

        return res

Time & Space Complexity

Time complexity: $O(26 * n)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

7. First And Last Index (Optimal)

Intuition

The previous approach uses a set to track distinct middle characters, which has some overhead. We can use a bitmask instead, where each bit represents whether a character has been seen. This provides O(1) operations for checking and adding characters.

Algorithm

First pass: Record the first and last index of each character in the string.
For each character that appears at least twice:
- Let l = firstIndex and r = lastIndex.
- Initialize a bitmask mask = 0.
- For each index from l+1 to r-1:
  - If the character at that index is not already in the mask, add it and increment the result.
- The mask tracks which middle characters we've already counted.
Return the total count.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        firstIndex = [-1] * 26
        lastIndex = [-1] * 26

        for i in range(len(s)):
            j = ord(s[i]) - ord('a')
            if firstIndex[j] == -1:
                firstIndex[j] = i
            lastIndex[j] = i

        res = 0
        for ends in range(26):
            if firstIndex[ends] == -1 or firstIndex[ends] == lastIndex[ends]:
                continue
            l, r = firstIndex[ends], lastIndex[ends]
            mask = 0
            for i in range(l + 1, r):
                c = ord(s[i]) - ord('a')
                if mask & (1 << c):
                    continue
                mask |= (1 << c)
                res += 1

        return res

Time & Space Complexity

Time complexity: $O(26 * n)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Common Pitfalls

Counting Subsequences Instead of Unique Palindromes

The problem asks for the count of unique palindromic subsequences, not the total number of subsequences. A palindrome like "aba" should only be counted once even if it appears multiple times in the string at different positions. Failing to use a set or similar deduplication mechanism leads to overcounting.

Not Understanding the Subsequence Definition

A subsequence does not require consecutive characters. Some solutions incorrectly look for contiguous substrings of length 3 instead of subsequences where the three characters can have any number of characters between them. The characters just need to maintain their relative order.

Inefficient Middle Character Counting

For each pair of matching end characters, you need to count distinct middle characters between the first and last occurrence. Iterating through the entire substring for each end character pair works but can be slow. The optimal approach uses prefix sums or bitmasks to efficiently count distinct characters in any range.