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.
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; }}Video 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.