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 <iostream>
2#include <unordered_map>
3using namespace std;
4
5int wonderfulSubstrings(string word) {
6 unordered_map<int, int> prefixStatus = {{0, 1}};
7 int currStatus = 0, count = 0;
8
9 for (char c : word) {
10 currStatus ^= (1 << (c - 'a'));
11 count += prefixStatus[currStatus];
12 for (int i = 0; i < 10; i++) {
13 count += prefixStatus[currStatus ^ (1 << i)];
14 }
15 prefixStatus[currStatus]++;
16 }
17
18 return count;
19}
20
21int main() {
22 cout << wonderfulSubstrings("aba") << endl;
23 return 0;
24}
25This solution in C++ implements a similar logic to the C version but uses an unordered map for more efficient prefix status tracking. The same toggling logic is applied for character status checks, counting possible wonderful substrings.
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.