Code Implementation

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        from collections import defaultdict
        count = defaultdict(int)
        count[0] = 1
        res = 0
        mask = 0
        for ch in word:
            mask ^= 1 << (ord(ch) - ord('a'))
            res += count[mask]
            for i in range(10):
                res += count[mask ^ (1 << i)]
            count[mask] += 1
        return res
      

class Solution {
public:
    long long wonderfulSubstrings(string word) {
        vector<long long> count(1024, 0);
        count[0] = 1;
        int mask = 0;
        long long res = 0;
        for (char ch : word) {
            mask ^= 1 << (ch - 'a');
            res += count[mask];
            for (int i = 0; i < 10; ++i) {
                res += count[mask ^ (1 << i)];
            }
            count[mask]++;
        }
        return res;
    }
};
      

class Solution {
    public long wonderfulSubstrings(String word) {
        long[] count = new long[1024];
        count[0] = 1;
        int mask = 0;
        long res = 0;
        for (char ch : word.toCharArray()) {
            mask ^= 1 << (ch - 'a');
            res += count[mask];
            for (int i = 0; i < 10; i++) {
                res += count[mask ^ (1 << i)];
            }
            count[mask]++;
        }
        return res;
    }
}
      

var wonderfulSubstrings = function(word) {
    const count = new Array(1024).fill(0);
    count[0] = 1;
    let res = 0, mask = 0;
    for (let ch of word) {
        mask ^= 1 << (ch.charCodeAt(0) - 'a'.charCodeAt(0));
        res += count[mask];
        for (let i = 0; i < 10; i++) {
            res += count[mask ^ (1 << i)];
        }
        count[mask]++;
    }
    return res;
};
      

Problem Description

• A substring is a contiguous sequence of characters within the string.
• Each substring may be empty or contain any number of characters from word.
• At most one letter can appear an odd number of times in a wonderful substring.
• Return the total count of all such substrings.

Thought Process

• We only care about the parity (odd/even) of each character's count, not the exact count.
• There are only 10 possible letters, so we can represent the parity of all letters using a 10-bit bitmask.
• If two prefixes have the same bitmask, the substring between them has all even counts for each letter.
• To allow for one odd count, we can flip each bit in the mask and check if we've seen that state before.

Solution Approach

1. Bitmask Representation: Since only letters 'a' to 'j' are present, use a 10-bit integer to represent the odd/even status of each letter in the current prefix. For example, if 'a' and 'c' have odd counts, the bitmask is 101 (binary).
2. Prefix Mask Counting: As we iterate through the string, maintain a current bitmask. For each character, flip the bit corresponding to that character.
3. Hash Map Storage: Keep a hash map (or array) to count how many times each mask has occurred so far. This allows us to quickly compute how many substrings ending at the current position are wonderful.
4. Counting Wonderful Substrings:
   • For a substring to have all even counts (zero odd counts), the prefix masks at the start and end must be equal. So, add the number of times the current mask has been seen.
   • For a substring to have exactly one odd count, the masks should differ by exactly one bit. For each bit position (0 to 9), flip that bit in the current mask and add the count of that mask.
5. Iterate and Accumulate: For each character, perform the above checks and update the hash map with the new mask occurrence.

Example Walkthrough

• Initialize mask = 0 and count[0] = 1.
• First character 'a':
  • Flip bit 0: mask = 1.
  • No previous mask 1, but for each bit flip, only mask 0 exists (count is 1), so add 1.
  • Update count[1] = 1.
• Second character 'b':
  • Flip bit 1: mask = 3 (binary 11).
  • No previous mask 3. For each bit flip:
    • mask 2 (flip bit 0): count 0
    • mask 1 (flip bit 1): count 1
    • Others: count 0
  • Add 1 for mask 1, update count[3] = 1.
• Third character 'a':
  • Flip bit 0: mask = 2 (binary 10).
  • No previous mask 2. For each bit flip:
    • mask 3 (flip bit 0): count 1
    • mask 0 (flip bit 1): count 1
    • Others: count 0
  • Add 1 for mask 3, 1 for mask 0, update count[2] = 1.

Time and Space Complexity

• Brute-force: O(n³) time (O(n²) substrings, O(n) to count frequencies), O(1) space.
• Optimized (bitmask):
  • Time: O(n * 10) = O(n), since for each character we check at most 11 masks (current + 10 bit flips).
  • Space: O(2¹⁰) = O(1), since there are at most 1024 possible mask states.

Summary