Sponsored
Sponsored
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.
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.
1def countUniquePalindromes(s):
2 n = len(s)
3 result = set()
4 after = [{} for _ in range(n)]
5 before = [{} for _ in range(n)]
6
7 for i in range(n - 2, -1, -1):
8 after[i] = after[i + 1].copy()
9 after[i][s[i + 1]] = after[i].get(s[i + 1], 0) + 1
10
11 for i in range(1, n - 1):
12 c = s[i]
13 before[i] = before[i - 1].copy()
14 before[i][s[i - 1]] = before[i].get(s[i - 1], 0) + 1
15
16 for ch in before[i]:
17 if ch in after[i]:
18 result.add((ch, c, ch))
19
20 return len(result)
21
22# Example Usage
23s = "aabca"
24print(countUniquePalindromes(s)) # Output: 3The 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.
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.
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.
1import java.util.HashSet;
2
The Java solution employs a similar two-pointer strategy, iterating over possible positions for 'a' and another 'a', while searching for middle 'b' between them. Each unique palindrome is added to a set.