Unique Length-3 Palindromic Subsequences

How it works

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.

Steps

1. First pass: Record the first and last index of each character in the string.
2. 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.
3. Return the total count.

Complexity

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

Things to watch for

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.

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

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<int> firstIndex(26, -1);
        vector<int> lastIndex(26, -1);

        for (int i = 0; i < s.size(); i++) {
            int j = s[i] - 'a';
            if (firstIndex[j] == -1) {
                firstIndex[j] = i;
            }
            lastIndex[j] = i;
        }

        int res = 0;
        for (int ends = 0; ends < 26; ends++) {
            if (firstIndex[ends] == -1 || firstIndex[ends] == lastIndex[ends]) {
                continue;
            }
            int l = firstIndex[ends], r = lastIndex[ends];
            int mask = 0;
            for (int i = l + 1; i < r; i++) {
                int c = s[i] - 'a';
                if (mask & (1 << c)) {
                    continue;
                }
                mask |= (1 << c);
                res++;
            }
        }
        return res;
    }
};