#1930

Medium

LeetCode Problem Workspace

Unique Length-3 Palindromic Subsequences

Count all unique length-3 palindromic subsequences in a string efficiently using hash tables and character positions.

hash table string bit manipulation prefix sum

Problem Statement

Given a string s consisting only of lowercase letters, determine the number of unique palindromes of exactly length three that appear as subsequences in s. Each subsequence must maintain relative order from s, and repeated subsequences are counted only once.

A palindrome reads identically forwards and backwards. Your task is to return the total count of all distinct length-3 palindromic subsequences present in s, focusing on efficiently handling character positions and frequency patterns.

Examples

Example 1

Input: s = "aabca"

Output: 3

The 3 palindromic subsequences of length 3 are:

"aba" (subsequence of "aabca")
"aaa" (subsequence of "aabca")
"aca" (subsequence of "aabca")

Example 2

Input: s = "adc"

Output: 0

There are no palindromic subsequences of length 3 in "adc".

Example 3

Input: s = "bbcbaba"

Output: 4

The 4 palindromic subsequences of length 3 are:

"bbb" (subsequence of "bbcbaba")
"bcb" (subsequence of "bbcbaba")
"bab" (subsequence of "bbcbaba")
"aba" (subsequence of "bbcbaba")

Constraints

3 <= s.length <= 105
s consists of only lowercase English letters.

Solution Approach

Track Character Positions

Use a hash table to store the first and last index of each character. For each character considered as the outer character of a length-3 palindrome, identify possible middle characters appearing between these positions.

Count Unique Subsequences

Iterate through all characters as outer characters. For each, collect distinct middle characters in a set to ensure uniqueness. The number of unique middle characters for each outer character pair contributes to the total count.

Optimize with Fixed Alphabet

Since the string contains only lowercase letters, precompute first and last positions for all 26 letters. This reduces unnecessary scanning and guarantees O(n) time with constant extra space.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because we scan the string once and check fixed 26 letters for each character. Space complexity is O(1) since only a constant-size array or hash table for 26 letters is used.

What Interviewers Usually Probe

Can you find a linear-time approach without generating all subsequences explicitly?
How would you handle counting duplicates efficiently for the same outer character?
Consider leveraging the fixed alphabet size to simplify the solution.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all length-3 subsequences leads to O(n^3) time and timeouts.
Counting duplicate palindromes multiple times instead of using sets or hash tables.
Ignoring the character position constraints when identifying valid middle characters.

Follow-up variants

Count unique length-4 palindromic subsequences with the same hash table approach.
Return all unique length-3 palindromic subsequences instead of just counting them.
Apply the same method to strings with digits or uppercase letters by expanding the hash table.

FAQ

What is the fastest way to count unique length-3 palindromic subsequences?

Use a hash table to track first and last occurrences of each character and then collect unique middle characters for each outer pair.

Can this method handle strings up to length 10^5?

Yes, the O(n) linear approach with constant space scales efficiently for strings of maximum allowed length.

Why do we use a set for middle characters?

Using a set ensures that duplicates are not counted multiple times for the same outer character, preserving uniqueness.

Does this approach extend to palindromes longer than 3 characters?

The same outer-inner indexing idea works, but longer lengths require careful nested iteration or additional prefix tracking.

How does this relate to the Hash Table plus String pattern?

The pattern is applied by mapping characters to positions in a hash table and using string indices to efficiently find valid palindromic subsequences.

terminal

Solution

Solution 1: Enumerate Both End Characters + Hash Table

Since the string contains only lowercase letters, we can directly enumerate all pairs of end characters. For each pair of end characters $c$, we find their first and last occurrence positions $l$ and $r$ in the string. If $r - l > 1$, it means we have found a palindromic subsequence that meets the conditions. We then count the number of unique characters between $[l+1,..r-1]$, which gives the number of palindromic subsequences with $c$ as the end characters, and add it to the answer.

1

2

3

4

5

6

7

8

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        for c in ascii_lowercase:
            l, r = s.find(c), s.rfind(c)
            if r - l > 1:
                ans += len(set(s[l + 1 : r]))
        return ans

Continue Practicing

#1915 number of wonderful substrings #1371 find the longest substring containing vowels in even counts #1177 can make palindrome from substring