Unique Length-3 Palindromic Subsequences

Unique Length-3 Palindromic Subsequences

What is this problem about?

The Unique Length-3 Palindromic Subsequences interview question asks you to count the number of unique palindromic subsequences of length 3 in a given string. A palindrome of length 3 is a string where the first and last characters are the same (e.g., "aba", "zaz"). Because we are looking for subsequences, the characters do not need to be contiguous in the original string.

Why is this asked in interviews?

This Unique Length-3 Palindromic Subsequences coding problem is frequently seen at Microsoft and Meta. it tests your ability to optimize search logic. While a brute-force approach (checking all triplets) is $O(n^3)$, interviewers expect you to find a more efficient solution, usually $O(26*n)$ or $O(n)$, by leveraging the constraints of the problem (length 3 and a limited alphabet).

Algorithmic pattern used

The primary Hash Table, String, Bit Manipulation, Prefix Sum interview pattern for this involves focusing on the characters that can serve as the "outer" part of the palindrome. For each character from 'a' to 'z', you find its first and last occurrence in the string. Any character that exists between these two indices in the original string can serve as the "middle" character of a palindrome. By counting the unique middle characters for each 'a'-'z' pair, you find all unique length-3 palindromes.

Example explanation

Consider the string "aabca".

1. For character 'a': First index is 0, last is 4.
2. The characters between indices 0 and 4 are 'a', 'b', and 'c'.
3. This gives us three palindromes: "aaa", "aba", and "aca".
4. For character 'b': It only appears once, so no palindrome can start and end with 'b'. Total unique palindromes: 3.

Common mistakes candidates make

The biggest mistake is overcomplicating the logic with complex dynamic programming. For a fixed length of 3, a simpler approach is almost always better. Candidates also often forget to only count unique palindromes; using a Set for the middle characters is essential to avoid duplicates like "aaa" being counted multiple times if 'a' appears multiple times in the middle.

Interview preparation tip

When a problem specifies a very small, fixed size (like length 3), look for ways to iterate over the possible "shell" of the structure. In this case, the shell is the two identical outer characters. Mastering the use of First and Last Index tracking is a very useful trick for subsequence problems.