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.
1from collections import defaultdict
2
3def wonderful_substrings(word):
4 prefix_status = defaultdict(int)
5 prefix_status[0] = 1
6 curr_status, count = 0, 0
7
8 for c in word:
9 curr_status ^= (1 << (ord(c) - ord('a')))
10 count += prefix_status[curr_status]
11 for i in range(10):
12 count += prefix_status[curr_status ^ (1 << i)]
13 prefix_status[curr_status] += 1
14
15 return count
16
17print(wonderful_substrings("aba"))
18Python’s defaultdict is leveraged for prefix tracking. The iterative process through each character in the string checks the current character's bit-state, adjusts the `prefix_status`, and accumulates the count of wonderful substrings based on state proximity.
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.