Unique Length-3 Palindromic Subsequences: First and Last Occurrence

June 5, 20265 min read

leetcodeproblemmediumstringshash-map

LeetCode 1930, Unique Length-3 Palindromic Subsequences, asks you to count how many unique palindromic subsequences of length 3 exist in a given string s. A palindrome of length 3 looks like "aba", where the first and third characters are the same and the middle character can be anything. You are not looking for substrings (contiguous), but subsequences (characters can be non-adjacent as long as their order is preserved).

Example: s = "aabca" returns 3. The unique length-3 palindromic subsequences are "aaa", "aba", and "aca".

For s = "aabca", the first 'a' is at index 0 and the last 'a' is at index 4. Between them are three distinct characters (a, b, c), giving three palindromes: "aaa", "aba", "aca".

Why this problem matters

This problem is a great example of an observation-based string problem. The brute force approach of checking all possible triplets is O(n^3), which is far too slow for strings up to 100,000 characters. But one clean observation about palindrome structure reduces the entire problem to a single pass through the alphabet. If you enjoy problems where a shift in perspective eliminates most of the work, this one is worth studying.

The key observation

A length-3 palindrome has the form c ? c, where c is some character and ? is any character in between. For a specific outer character c, every valid palindrome uses one occurrence of c on the left and one on the right with some character sandwiched in the middle.

Here is the trick: you do not need to find every pair of c values. You only need the first and last occurrence of c in the string. Any character that appears between those two positions can serve as the middle character of a valid palindrome. And since you want unique palindromes, you just need the number of distinct characters between the first and last occurrence.

Why the first and last? Because any pair of c positions that are closer together would have fewer (or equal) characters between them. The first and last occurrence gives you the widest possible window, capturing every character that could ever appear as a middle element.

This is a common pattern in string problems: when you need to maximize the range of characters between two matching endpoints, always use the first and last occurrence. It guarantees you never miss a valid middle character.

So the algorithm is:

For each of the 26 lowercase letters, find its first and last position in s.
If the letter appears at least twice (first and last positions are different), collect all distinct characters between those two positions.
The count of distinct middle characters is the number of unique palindromes with that outer character.
Sum across all 26 letters.

The solution

def count_palindromic_subsequence(s: str) -> int:
    result = 0
    for c in set(s):
        first = s.index(c)
        last = s.rindex(c)
        if first < last:
            middles = set(s[first + 1:last])
            result += len(middles)
    return result

Step 1: Check outer char 'a'. First at index 0, last at index 4.

Between index 0 and 4, the distinct characters are {a, b, c}. That gives 3 palindromes: "aaa", "aba", "aca".

Step 2: Check outer char 'b'. First at index 2, last at index 2.

'b' appears only once. First and last positions are the same, so there are no characters in between. 0 palindromes.

Step 3: Check outer char 'c'. First at index 3, last at index 3.

'c' appears only once. No room for a middle character. 0 palindromes.

Result: Total unique length-3 palindromic subsequences = 3 + 0 + 0 = 3.

Only 'a' contributes palindromes. The answer is 3.

Practice this problem with spaced repetition

Let's walk through what each piece does:

for c in set(s) iterates over every distinct character in the string. At most 26 iterations.
s.index(c) finds the first occurrence of c. s.rindex(c) finds the last occurrence.
if first < last ensures the character appears at least twice. If it only appears once, there is no room for a middle character.
set(s[first + 1:last]) collects the distinct characters between the first and last occurrence. The size of this set is exactly the number of unique palindromes with c as the outer character.
We add that count to result and move on to the next character.

Be careful with the slice boundaries. You want s[first + 1:last], not s[first:last]. Including the first occurrence itself in the middle set would be fine for correctness (since c could also be a valid middle character), but the slice should start one position after first and end one position before last to correctly represent "between" the two endpoints.

Complexity analysis

Approach	Time	Space
First/last + set	O(26 * n) = O(n)	O(1)

Time: O(n). You iterate through at most 26 characters. For each one, finding the first and last occurrence is O(n), and building the set of middle characters is O(n). So it is 26 * O(n) = O(n).

Space: O(1). The set of middle characters contains at most 26 elements. The set of distinct characters in s is also at most 26. Everything is bounded by a constant.

Edge cases to watch for

All identical characters. If s = "aaaaa", the only outer character is 'a'. The middle set is {'a'}. The answer is 1, just "aaa".
All distinct characters. If s = "abcde", no character appears twice. The answer is 0.
Two occurrences with nothing between them. If s = "aa", the first 'a' is at index 0 and the last is at index 1. The slice s[1:1] is empty, so the middle set is empty. The answer is 0. You need at least one character between the two outer positions.
String of length 3. The minimum case where a palindrome is possible. s = "aba" gives 1. s = "abc" gives 0.

The building blocks

This problem is built from one core technique that appears across many string problems: the first and last occurrence pattern.

The idea is simple. When you need to know the maximum range a character spans in a string, precompute or query the first and last index of that character. This gives you the widest window to work with. You have already seen this concept if you have worked on problems like Longest Repeating Character Replacement or Minimum Window Substring, where tracking character positions within a range is the central operation.

The second building block is set-based counting. Instead of tracking individual subsequences (which would be combinatorially explosive), you reduce the question to "how many distinct elements exist in this range?" A set handles deduplication automatically.

Together, these two ideas, first/last occurrence and set-based counting, turn an O(n^3) brute force into an O(n) one-liner per character.

Drill the first/last occurrence pattern

From understanding to recall

This problem has a satisfying "aha" moment when you realize the first and last occurrence trick. But that moment fades quickly. Two weeks from now, when you see a similar problem about counting distinct subsequences in a range, will you immediately think "find the widest window using first and last positions"?

The building block here is small: for each character, find its first and last index, then count distinct values in between. That is the pattern. Spaced repetition helps you lock in the connection between "palindromic subsequence" and "first/last occurrence window." After a few review cycles, the approach fires automatically. You skip the part where you stare at the problem wondering how to avoid brute force, because the observation is already part of your toolkit.

Group Anagrams - String character counting pattern
Palindrome Partitioning - Another palindrome analysis problem
Longest Palindromic Substring - Classic palindrome problem

Try CodeBricks free