Problem Description
Given a string s, return the number of unique palindromes of length three that are a subsequence of s. 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.
Key Insights
- A palindromic subsequence of length 3 can be represented as "aba", where 'a' is the first and last character and 'b' is the middle character.
- We need to find all unique combinations of characters in the string that can form this pattern.
- We can utilize a hash table to count occurrences of characters and their indices to efficiently determine valid subsequences.
- The maximum length of the input string (100,000) requires an O(n) solution to ensure performance.
Space and Time Complexity
Time Complexity: O(n^2), where n is the length of the string. We iterate through the string to create pairs and check for valid palindromic sequences. Space Complexity: O(n) for storing the last seen indices of characters.
Solution
To solve the problem, we can use a hash table to store the last seen indices of each character as we iterate through the string. For each character, we check if it can form a palindrome with previously seen characters. We can collect unique palindromic subsequences in a set to ensure they are counted only once.