Sponsored
Sponsored
This approach uses bitmasking to track the odd/even status of character frequencies. We use a prefix sum technique to maintain these statuses as the string is iterated upon.
Time Complexity: O(n * k), where n is the length of the string and k is 10 (number of possible characters).
Space Complexity: O(2^k), due to the prefixStatus array for bitmasking.
1#include <stdio.h>
2#include <string.h>
3
4int wonderfulSubstrings(char* word) {
5 int prefixStatus[1024] = {1}; // 2^10 states initialized
6 int currStatus = 0, count = 0;
7
8 for (; *word != '\0'; word++) {
9 currStatus ^= (1 << (*word - 'a'));
10 count += prefixStatus[currStatus];
11 for (int i = 0; i < 10; i++)
12 count += prefixStatus[currStatus ^ (1 << i)];
13 prefixStatus[currStatus]++;
14 }
15
16 return count;
17}
18
19int main() {
20 char word[] = "aba";
21 printf("%d\n", wonderfulSubstrings(word));
22 return 0;
23}
24The `wonderfulSubstrings` function maintains a `prefixStatus` array where each index represents a binary mask of counts for characters 'a' to 'j'. For each character, we toggles its corresponding bit in `currStatus`. The current status is checked against previous statuses recorded in `prefixStatus` to calculate substrings. Additionally, substrings differing by only one bit (one odd letter) are also counted.
This approach uses a non-optimized sliding window technique over the string to identify all substrings and individually verify their "wonderfulness" by counting character frequencies.
Time Complexity: O(n^3),
Space Complexity: O(1).
1def is_wonderful(substr):
2 freq = [0] * 10
3
This solution in Python uses a nested loop to generate all possible substrings of the given word. The auxiliary function `is_wonderful` checks each substring to see if at most one character has an odd frequency, defining it as wonderful.