Unique Length-3 Palindromic Subsequences - Video Solutions

Problem Overview: Given a string s, count how many unique palindromic subsequences of length 3 exist. A valid subsequence has the pattern a ? a where the first and last characters are the same and the middle character can be anything, but each resulting palindrome must be counted only once.

Approach 1: Character Frequency and Set Method (O(n) time, O(1) space)

This approach leverages the fact that a length‑3 palindrome must look like c x c. For each character from 'a' to 'z', find its first and last occurrence in the string. If both exist and there is at least one character between them, every unique character inside that range can serve as the middle element. Use a set to collect distinct middle characters between the two indices, then add the set size to the answer. The alphabet size is fixed (26), so scanning for each character keeps the overall complexity linear. This method relies on simple lookups and is a natural application of a hash table or set for uniqueness while iterating through the string.

Approach 2: Two-Pointer Sliding Window with Prefix Tracking (O(n) time, O(1) space)

This method processes the string while maintaining information about characters seen on the left and characters remaining on the right. A frequency array or bitmask tracks which characters still appear ahead. As you move a pointer through the string, treat the current character as the potential middle of the palindrome. If a character exists both in the left side and the right side, it can form c middle c. Bitmasks or boolean arrays help detect these matches efficiently without storing large sets. This strategy resembles a sliding window combined with prefix/suffix tracking and can be implemented using compact operations common in bit manipulation or lightweight prefix counts similar to a prefix sum pattern.

Recommended for interviews: The character frequency and set method is usually the expected solution. It clearly demonstrates the key observation that the first and last occurrences of each character define the possible palindromes. A brute-force approach checking all subsequences would be O(n³) and impractical. Showing that baseline reasoning is useful, but the O(n) solution proves you can recognize structural constraints in the problem and reduce the search space efficiently.