Skip to main content
Talentd

Unique Length-3 Palindromic Subsequences - Solution & Explanation

MediumHash TableStringBit ManipulationPrefix Sum15 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

 

Example 1:

Input: s = "aabca"
Output: 3
Explanation: 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
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: 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.

Approach Overview

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.

Approach 1: Character Frequency and Set Method

This approach focuses on tracking the occurrence of characters in the string and how they can form palindromes. We maintain a set of palindromic subsequences to ensure uniqueness.

We iterate through the string, and for each character, we find possible 'b' for our 'aba' structure by looking at all characters that occurred before and after in the string. By maintaining sets of characters seen before and characters seen after each index, we can efficiently determine possible 'a' characters for our palindrome. After finding valid 'aba' subsequences, we add these to a set to ensure each palindrome is only counted once.

The solution iterates through the string, updating dictionaries to maintain counts of characters seen before and after each index. For each possible middle character, it checks if it can form a palindrome with any character that appears before and after the current character using the dictionaries to track these possibilities. Subsequence palindromes are stored in a set to ensure they are counted uniquely.

Code

PythonC

Python

C

Complexity

Time Complexity: O(n^2), where n is the length of the string, primarily due to the dictionary operations for checking palindromic conditions.

Space Complexity: O(1) additional space beyond input storage and result tracking.

Try this approach in the editor →

Approach 2: Two-Pointer Sliding Window

This approach simplifies processing using a two-pointer technique to fix the letters 'a' at the two ends of the palindrome and then check for any characters in between that can be 'b'. We count each found sequence as one unique palindrome. This results in a quick search for matching pairs with just linear passes for each character.

This JavaScript solution uses a two-pointer approach to fix the beginning and end 'a' characters of potential palindromes. By iterating between these two pointers, it identifies potential middle 'b' characters, storing each unique palindrome as a string in a set. This ensures no duplicate palindromes are counted.

Code

JavaScriptJava

JavaScript

Java

Complexity

Time Complexity: O(n^3), where n is the length of the string, due to trying out all combinations for the middle character.

Space Complexity: O(n) due to storage of results in a set.

Try this approach in the editor →

Approach 3: 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.

After enumerating all pairs, we get the answer.

The time complexity is O(n times |\Sigma|), where n is the length of the string and \Sigma is the size of the character set. In this problem, |\Sigma| = 26. The space complexity is O(|\Sigma|) or O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Character Frequency and Set Method

Time Complexity: O(n^2), where n is the length of the string, primarily due to the dictionary operations for checking palindromic conditions.

Space Complexity: O(1) additional space beyond input storage and result tracking.

Two-Pointer Sliding Window

Time Complexity: O(n^3), where n is the length of the string, due to trying out all combinations for the middle character.

Space Complexity: O(n) due to storage of results in a set.

Enumerate Both End Characters + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Character Frequency and Set MethodO(n)O(1)Best general solution. Simple logic using first/last positions and a set for unique middle characters.
Two-Pointer Sliding Window with Prefix TrackingO(n)O(1)Useful when maintaining prefix/suffix character states or when implementing with bitmasks.

Video Solution

Unique Length-3 Palindromic Subsequences - Leetcode 1930 - Python • NeetCode • 28,043 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Unique Length-3 Palindromic Subsequences easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 73%. The difficulty comes from recognizing that only the first and last occurrence of each character matter, which reduces the search space from all subsequences to a linear scan.
Unique Length-3 Palindromic Subsequences Python/Java solution
Python implementations usually use a set to track distinct middle characters between the first and last occurrence of each letter. Java solutions commonly rely on HashSet or boolean arrays for the same purpose. Both achieve O(n) time and constant auxiliary space.
How to solve Unique Length-3 Palindromic Subsequences in O(n)?
First record the first and last index of each character. For a character c, any palindrome must look like c ? c. Collect all distinct characters between those two indices using a set and add the count to the answer. Since there are only 26 possible outer characters, the total processing remains linear in the length of the string.
What is the best approach for Unique Length-3 Palindromic Subsequences?
The most common solution iterates over each character as the outer pair of the palindrome. For every letter, find its first and last occurrence in the string and count the unique characters between them using a set. This runs in O(n) time with O(1) extra space because the alphabet size is fixed at 26.
Is Unique Length-3 Palindromic Subsequences asked at Google/Amazon/Meta?
This problem tests string processing, hashing, and observation of structural constraints, which are common interview themes at companies like Amazon, Google, and Meta. Variants involving palindromes, subsequences, and character frequency appear frequently in coding interviews.
What data structure is used in Unique Length-3 Palindromic Subsequences?
Typical solutions use sets or hash tables to ensure uniqueness of the middle character. Some implementations also use frequency arrays or bitmasks to track characters seen on the left and right while scanning the string.
What is the time complexity of Unique Length-3 Palindromic Subsequences?
The optimal solutions run in O(n) time. The algorithm scans the string and performs constant‑size operations for each of the 26 characters or maintains prefix/suffix counts while traversing once. Space complexity remains O(1) since only small arrays or sets of alphabet characters are stored.

Ready to solve this problem?

Practice Unique Length-3 Palindromic Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Palindromic Subsequences