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.
1import java.util.HashMap;
2
3public class WonderfulSubstrings {
4 public static int wonderfulSubstrings(String word) {
5 HashMap<Integer, Integer> prefixStatus = new HashMap<>();
6 prefixStatus.put(0, 1);
7 int currStatus = 0, count = 0;
8
9 for (char c : word.toCharArray()) {
10 currStatus ^= (1 << (c - 'a'));
11 count += prefixStatus.getOrDefault(currStatus, 0);
12 for (int i = 0; i < 10; i++) {
13 count += prefixStatus.getOrDefault(currStatus ^ (1 << i), 0);
14 }
15 prefixStatus.put(currStatus, prefixStatus.getOrDefault(currStatus, 0) + 1);
16 }
17
18 return count;
19 }
20
21 public static void main(String[] args) {
22 System.out.println(wonderfulSubstrings("aba"));
23 }
24}
25The Java solution utilizes a HashMap for prefix status, allowing dynamic and fast lookup of prefix statuses. The toggling and counting strategy remains consistent with C and C++.
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.