Unique Length-3 Palindromic Subsequences
MedPrompt
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 <= 105sconsists of only lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible subsequence of length three. It uses three nested loops to pick three characters from the string s at indices i, j, and k such that i < j < k. For each subsequence, it checks if it's a palindrome. A HashSet is used to store the unique palindromes found to avoid duplicates.
Algorithm
- Initialize an empty
HashSet<String>nameduniquePalindromes. - Use three nested loops with indices
i,j,kto iterate through all triplets where0 <= i < j < k < s.length(). - Inside the innermost loop, check if
s.charAt(i)is equal tos.charAt(k). - If they are equal, construct the palindrome string and add it to
uniquePalindromes. - Return the final size of the
uniquePalindromesset.
Walkthrough
The algorithm iterates through all possible combinations of three indices i, j, and k from the string s.
The conditions 0 <= i < j < k < s.length() ensure that we are forming a valid subsequence of length three.
For each triplet of indices, we check if the characters at the outer indices i and k are the same (s.charAt(i) == s.charAt(k)). If they are, we have found a palindromic subsequence.
The formed palindrome string, s.charAt(i)s.charAt(j)s.charAt(k), is added to a HashSet<String>. The use of a set automatically handles the uniqueness requirement; duplicate palindromes will not be added.
Finally, the size of the set gives the total number of unique length-3 palindromic subsequences.
import java.util.HashSet;import java.util.Set; class Solution { public int countPalindromicSubsequence(String s) { int n = s.length(); Set<String> uniquePalindromes = new HashSet<>(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (s.charAt(i) == s.charAt(k)) { uniquePalindromes.add("" + s.charAt(i) + s.charAt(j) + s.charAt(k)); } } } } return uniquePalindromes.size(); }}Complexity
Time
O(N³), where N is the length of the string `s`. The three nested loops lead to a cubic number of iterations.
Space
O(1). The `HashSet` stores the unique palindromes. Since there are only 26 lowercase English letters, the maximum number of unique length-3 palindromes is 26 (for the outer character) * 26 (for the middle character) = 676. This is a constant number, so the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to the cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
A more optimized approach involves iterating through each character of the string and considering it as the middle character of a potential palindrome. For each middle character at index j, we need to find an outer character c that appears both in the prefix s[0...j-1] and the suffix s[j+1...N-1]. By finding the intersection of unique characters in the prefix and suffix, we can form palindromes.
Algorithm
- Initialize an empty
HashSet<String>namedresult. - Iterate with an index
jfrom1ton-2to fix the middle characters.charAt(j). - For each
j, create two sets:leftfor unique characters ins[0...j-1]andrightfor unique characters ins[j+1...n-1]. - Iterate through the characters in the
leftset. - If a character
cfromleftis also present in therightset, form the palindrome stringc + s.charAt(j) + cand add it toresult. - Return the size of the
resultset.
Walkthrough
This method iterates through the string from index j = 1 to n-2, treating s.charAt(j) as the middle element of a palindrome c s.charAt(j) c.
For each j, we need to determine the set of available characters for the outer positions. An outer character c is valid if it exists at least once in the substring before j (the prefix) and at least once in the substring after j (the suffix).
We can find the unique characters in the prefix s.substring(0, j) and store them in a set, say leftChars.
Similarly, we find unique characters in the suffix s.substring(j + 1) and store them in rightChars.
Then, we iterate through all 26 lowercase letters. If a letter c is present in both leftChars and rightChars, it means we can form the palindrome c s.charAt(j) c.
We use a HashSet<String> to store these unique palindromes to get the final count.
import java.util.HashSet;import java.util.Set; class Solution { public int countPalindromicSubsequence(String s) { int n = s.length(); Set<String> result = new HashSet<>(); for (int j = 1; j < n - 1; j++) { Set<Character> left = new HashSet<>(); for (int i = 0; i < j; i++) { left.add(s.charAt(i)); } Set<Character> right = new HashSet<>(); for (int k = j + 1; k < n; k++) { right.add(s.charAt(k)); } for (char c : left) { if (right.contains(c)) { result.add("" + c + s.charAt(j) + c); } } } return result.size(); }}Complexity
Time
O(N²). The main loop runs N times. Inside the loop, constructing the `left` and `right` sets takes O(j) and O(N-j) time respectively, which sums to O(N). Thus, the total complexity is O(N * N).
Space
O(1). The sets `left`, `right`, and `result` all store a constant maximum number of elements (26 for character sets, 676 for the result set).
Trade-offs
Pros
More efficient than the brute-force O(N³) approach.
Cons
Still too slow for the given constraints, likely resulting in TLE.
Involves repeated computation as sets for prefixes and suffixes are rebuilt in each iteration.
The most efficient approach focuses on the structure of a length-3 palindrome, XYX. Instead of iterating through indices, we can iterate through all possible outer characters X (from 'a' to 'z'). For each X, we find its first and last occurrences in the string s. If X appears at least twice, any unique character Y found in the substring between these first and last occurrences can form a valid palindrome XYX. By summing up the counts of these unique middle characters for each possible X, we get the total number of unique palindromes.
Algorithm
- Initialize a counter
totalUniquePalindromesto 0. - Loop through each character
cfrom 'a' to 'z'. - Inside the loop, find the index of the first occurrence of
c(firstIndex) and the last occurrence ofc(lastIndex) in the strings. - If
cexists in the string andfirstIndex < lastIndex, proceed. - Create a
HashSet<Character>to store the unique characters in the substrings.substring(firstIndex + 1, lastIndex). - Iterate from
firstIndex + 1tolastIndex - 1and add each character to the set. - Add the size of the set to
totalUniquePalindromes. - After checking all 26 characters, return
totalUniquePalindromes.
Walkthrough
The core idea is that for any unique palindrome XYX, X must appear at least twice in the string s.
We can iterate through each character c from 'a' to 'z', considering it as the potential outer character X.
For each character c, we find its first index (firstIndex) and last index (lastIndex) in the string s.
If firstIndex is -1 or firstIndex is the same as lastIndex, it means c appears less than twice, so it cannot form the outer boundary of a length-3 palindrome. We skip to the next character.
If firstIndex < lastIndex, we have a valid pair of outer characters. The middle character Y can be any character present in the substring between these two indices, i.e., s.substring(firstIndex + 1, lastIndex).
To find the number of unique palindromes for this outer character c, we just need to count the number of unique characters in this middle substring. A HashSet<Character> or a boolean array of size 26 can be used for this.
We add this count of unique middle characters to our total result. The final sum across all 26 possible outer characters is the answer.
import java.util.HashSet;import java.util.Set; class Solution { public int countPalindromicSubsequence(String s) { int totalUniquePalindromes = 0; // Iterate through all possible outer characters ('a' through 'z') for (char c = 'a'; c <= 'z'; c++) { int firstIndex = s.indexOf(c); int lastIndex = s.lastIndexOf(c); // Check if the character exists and appears at least twice if (firstIndex != -1 && firstIndex < lastIndex) { // A gap of at least 1 is needed for the middle character if (lastIndex > firstIndex + 1) { // Find unique characters in the substring between the first and last occurrence Set<Character> middleChars = new HashSet<>(); for (int i = firstIndex + 1; i < lastIndex; i++) { middleChars.add(s.charAt(i)); } totalUniquePalindromes += middleChars.size(); } } } return totalUniquePalindromes; }}Complexity
Time
O(N). The main loop runs a constant 26 times. Inside the loop, `indexOf` and `lastIndexOf` take O(N) time. Finding unique characters in the substring also takes O(N) in the worst case. The total time complexity is O(26 * N), which simplifies to O(N).
Space
O(1). In each iteration of the outer loop, a `HashSet` is used to store middle characters. Since there are only 26 possible lowercase letters, the size of this set is bounded by a constant. Therefore, the space complexity is O(1).
Trade-offs
Pros
Highly efficient with linear time complexity.
Conceptually clean and directly maps to the problem's structure.
Passes all constraints with ease.
Cons
Slightly more complex than brute-force but the performance gain is massive.
Solutions
Solution
public class Solution { public int CountPalindromicSubsequence(string s) { int ans = 0; for (char c = 'a'; c <= 'z'; ++c) { int l = s.IndexOf(c), r = s.LastIndexOf(c); HashSet < char > cs = new HashSet < char > (); for (int i = l + 1; i < r; ++i) { cs.Add(s[i]); } ans += cs.Count; } return ans; }}class Solution {public int countPalindromicSubsequence(String s) { int ans = 0; for (char c = 'a'; c <= 'z'; ++c) { int l = s.indexOf(c), r = s.lastIndexOf(c); Set<Character> cs = new HashSet<>(); for (int i = l + 1; i < r; ++i) { cs.add(s.charAt(i)); } ans += cs.size(); } return ans; }}export function countPalindromicSubsequence ( s ) { const cnt = new Map (); const n = s . length ; let ans = 0 ; for ( let i = 0 ; i < n ; i ++ ) { const ch = s [ i ]; if ( cnt . has ( ch )) cnt . get ( ch )[ 1 ] = i ; else cnt . set ( ch , [ i , i ]); } for ( const [ _ , [ i , j ]] of cnt ) { if ( i !== j ) { ans += new Set ( s . slice ( i + 1 , j )). size ; } } return ans ; }class Solution {public: int countPalindromicSubsequence(string s) { int ans = 0; for (char c = 'a'; c <= 'z'; ++c) { int l = s.find_first_of(c), r = s.find_last_of(c); unordered_set<char> cs; for (int i = l + 1; i < r; ++i) cs.insert(s[i]); ans += cs.size(); } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.