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.
1function wonderfulSubstrings(word) {
2 const prefixStatus = {0: 1};
3 let currStatus = 0, count = 0;
4
5 for (const char of word) {
6 currStatus ^= (1 << (char.charCodeAt(0) - 'a'.charCodeAt(0)));
7 count += prefixStatus[currStatus] || 0;
8 for (let i = 0; i < 10; i++) {
9 count += prefixStatus[currStatus ^ (1 << i)] || 0;
10 }
11 prefixStatus[currStatus] = (prefixStatus[currStatus] || 0) + 1;
12 }
13
14 return count;
15}
16
17console.log(wonderfulSubstrings("aba"));
18JavaScript's object-based approach mimics a hashmap for tracking prefix statuses. Each character toggles bits in `currStatus` to keep an updated state, subsequently checking direct and near-states to compute the count of 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.