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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int WonderfulSubstrings(string word) {
6 var prefixStatus = new Dictionary<int, int>();
7 prefixStatus[0] = 1;
8 int currStatus = 0, count = 0;
9
10 foreach (char c in word) {
11 currStatus ^= (1 << (c - 'a'));
12 count += prefixStatus.ContainsKey(currStatus) ? prefixStatus[currStatus] : 0;
13 for (int i = 0; i < 10; i++) {
14 count += prefixStatus.ContainsKey(currStatus ^ (1 << i)) ? prefixStatus[currStatus ^ (1 << i)] : 0;
15 }
16 if (!prefixStatus.ContainsKey(currStatus)) {
17 prefixStatus[currStatus] = 0;
18 }
19 prefixStatus[currStatus]++;
20 }
21
22 return count;
23 }
24
25 public static void Main() {
26 Solution sol = new Solution();
27 Console.WriteLine(sol.WonderfulSubstrings("aba"));
28 }
29}
30The C# solution uses a Dictionary for prefix status tracking. As word characters are processed, the parity of appearances is maintained using bitwise operations, with systematic updates to the Dictionary to identify and count 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.