1930. Unique Length-3 Palindromic Subsequences - Detailed Explanation
Problem Statement
Given a string s, return the number of unique palindromic subsequences of length 3 in s. A subsequence is derived from s by deleting some or no characters without changing the order of the remaining characters. A palindrome is a string that reads the same forward and backward.
Example 1
Input: s = "aabca"
Output: 3
Explanation: The unique palindromic subsequences of length 3 are "aba", "aaa", and "aca".
Example 2
Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3.
Constraints:
3 <= s.length <= 10^5sconsists of lowercase English letters.
Hints to Solve the Problem
- A length-3 palindrome has the format
x_y_x, where the first and last characters are the same (x) and the middle character can be any character (y). - First identify valid characters
xthat can serve as the outer characters of the palindrome. These would be characters that appear at least twice ins. - For each such character
x, look at the substring between its first and last occurrence ins. Any characterythat appears in between can form a palindromex_y_x. Using a hash set to collect these middle charactersyhelps track unique palindromes efficiently.
Approach 1: Brute Force (Generating All Length-3 Subsequences)
Explanation:
- Iterate through all possible triplets of indices
(i, j, k)inswithi < j < k. These represent all subsequences of length 3. - Check if the characters at those indices form a palindrome, i.e.,
s[i] == s[k]. If yes, thens[i]s[j]s[k]is a palindromic subsequence. - Use a set to keep track of distinct palindromic subsequences found, to ensure uniqueness.
- Count the size of the set at the end.
This brute-force approach tries every combination and thus is very slow for large strings, but it is straightforward to implement and understand.
Python Code:
Complexity Analysis:
- Time Complexity: O(N³) – Three nested loops generate all combinations of three indices. This is extremely inefficient for large
N(not feasible whenNis up to 100,000). - Space Complexity: O(P) – where P is the number of unique palindromic subsequences found (at most 26*26 in the worst case, because outer letters and middle letter are each among 26 lowercase letters). Apart from the output set, the space usage is O(1).
Java Code:
Approach 2: Optimized Using First and Last Occurrences (Efficient Solution)
Explanation:
Instead of brute-forcing all triplets, we can use the properties of palindromes:
-
Choose outer character
x: Iterate through each character from'a'to'z'(or through each unique character ins). Treat this character as the potential first and last character of a palindrome. -
Find first and last positions of
x: Use string search to find the first occurrence (first) and the last occurrence (last) ofxins. Ifxdoesn't appear at least twice, it can't form a length-3 palindrome, so skip it. -
Count unique middle characters
y: Look at the substring betweenfirst+1andlast-1(the part ofsstrictly between the first and lastx). Collect all distinct characters in this segment — each such character can serve as a middle characteryto form a palindromex_y_x. -
Add to count: The number of unique palindromic subsequences with
xas outer characters is exactly the number of distinct characters found in step 3. Accumulate this count for all possiblex.
By focusing on first and last occurrences of each character, we efficiently gather all possible palindromes without redundant checks.
Python Code:
Complexity Analysis:
- Time Complexity: O(26 * N) ≈ O(N). We iterate over at most 26 characters (the lowercase English alphabet). For each character, finding first and last occurrence is O(N), and collecting middle characters is also O(N) in the worst case. This simplifies to O(26*N) which is essentially O(N). In practice, this is very efficient even for large strings (up to 100k length).
- Space Complexity: O(1) extra space (not counting output). The set of middle characters uses at most 26 characters, and we reuse it for each outer character in sequence.
Java Code:
Edge Cases
- No valid palindromes:
s = "abc"→ Output:0(no character appears twice, so no length-3 palindrome exists). - All characters the same:
s = "aaaa"→ Output:1(only possible palindrome is"aaa"using any three of the characters). - Minimum length input:
s = "aba"→ Output:1(the string itself is the only length-3 palindrome subsequence).
Related Problems
- Longest Palindromic Subsequence: Find the longest palindromic subsequence in a string (dynamic programming problem).
- Count Distinct Subsequences: Count the number of distinct subsequences in a string (a different problem that also often involves DP or combinatorics).
GET YOUR FREE
Coding Questions Catalog
