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.
"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 <= 105s consists of only lowercase English letters.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.
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.
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.
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.
JavaScript
Java
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.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency and Set Method | O(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 Tracking | O(n) | O(1) | Useful when maintaining prefix/suffix character states or when implementing with bitmasks. |
Unique Length-3 Palindromic Subsequences - Leetcode 1930 - Python • NeetCode • 27,787 views views
Watch 9 more video solutions →Practice Unique Length-3 Palindromic Subsequences with our built-in code editor and test cases.
Practice on FleetCode