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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5#define ALPHABET_SIZE 26
6
7bool containsChar(char *set, char ch) {
8 return set[ch - 'a'];
9}
10
11void addToSet(char *set, char ch) {
12 set[ch - 'a'] = true;
13}
14
15int countUniquePalindromes(const char *s) {
16 int n = strlen(s);
17 int result = 0;
18 bool before[ALPHABET_SIZE] = {0};
19 bool after[ALPHABET_SIZE] = {0};
20 bool found[ALPHABET_SIZE][ALPHABET_SIZE] = {0};
21
22 for (int i = 0; i < n; i++)
23 addToSet(after, s[i]);
24
25 for (int i = 0; i < n; i++) {
26 after[s[i] - 'a'] = false;
27 for (int b = 0; b < ALPHABET_SIZE; b++) {
28 if (containsChar(before, b + 'a') && containsChar(after, b + 'a')) {
29 if (!found[s[i] - 'a'][b]) {
30 found[s[i] - 'a'][b] = true;
31 result++;
32 }
33 }
34 }
35 addToSet(before, s[i]);
36 }
37 return result;
38}
39
40int main() {
41 char s[] = "aabca";
42 printf("%d\n", countUniquePalindromes(s));
43 return 0;
44}This C solution operates similarly to the Python method. It uses boolean arrays to track the presence of characters before and after the current index. It checks if the current character can serve as the middle character in a palindromic subsequence based on conditions using these arrays.
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.