Problem Description

This problem asks us to count the number of "wonderful" substrings in a given string. A substring is considered wonderful if it contains at most one letter that appears an odd number of times.

The input string word consists only of the first 10 lowercase English letters ('a' through 'j').

Let's break down what makes a string wonderful:

• "ccjjc" is wonderful because 'c' appears 3 times (odd), while 'j' appears 2 times (even). Only one letter has an odd count.
• "abab" is wonderful because both 'a' and 'b' appear 2 times (even). No letters have odd counts.
• "ab" is NOT wonderful because both 'a' and 'b' appear 1 time each (odd). Two letters have odd counts.

The solution uses bit manipulation and prefix XOR to efficiently track character parity. The variable st maintains a bitmask where each bit represents whether a character ('a' to 'j') has appeared an odd number of times so far. When we XOR with 1 << (ord(c) - ord("a")), we flip the bit corresponding to character c.

The key insight is that a substring is wonderful if:

1. All characters appear an even number of times (XOR state matches a previously seen state)
2. Exactly one character appears an odd number of times (XOR state differs from a previously seen state by exactly one bit)

The algorithm counts substrings ending at each position by:

• Adding substrings where all characters have even counts: ans += cnt[st]
• Adding substrings where exactly one character has odd count: ans += cnt[st ^ (1 << i)] for each possible character position i

The Counter tracks how many times each XOR state has been seen, allowing us to count all valid substrings efficiently in O(n) time.

Intuition

The key observation is that checking if a substring is wonderful requires knowing the parity (odd/even count) of each character in that substring. Instead of checking every possible substring individually which would be O(n²) or worse, we can use a clever trick with XOR operations.

Think about what happens when we XOR a bit with itself: 1 ^ 1 = 0 and 0 ^ 0 = 0. This means if we see a character an even number of times, XORing will result in 0, and if we see it an odd number of times, the result is 1. This naturally tracks parity!

Since we only have 10 possible characters ('a' through 'j'), we can use a 10-bit integer where each bit represents whether that character has appeared an odd number of times in our current prefix. As we traverse the string, we flip the corresponding bit for each character we encounter.

Now comes the crucial insight: for a substring from index i to j to be wonderful, the XOR of the prefix states at positions i-1 and j must result in either:

1. Zero (all bits are 0) - meaning all characters in the substring appear an even number of times
2. A power of 2 (exactly one bit is 1) - meaning exactly one character appears an odd number of times

Instead of checking all pairs of indices, we can be smarter. At each position, we look for how many previous positions have:

• The exact same XOR state (this would give us substrings with all even counts)
• A XOR state that differs by exactly one bit (this would give us substrings with exactly one odd count)

By maintaining a frequency map of all XOR states we've seen so far, we can count valid substrings ending at the current position in constant time (well, O(10) since we check 10 possible single-bit differences). This reduces our overall complexity to O(n).

Learn more about Prefix Sum patterns.

Solution Approach

Let's walk through the implementation step by step:

1. Initialize the data structures:

cnt = Counter({0: 1})
ans = st = 0

• cnt is a frequency map that tracks how many times each XOR state has been seen. We initialize it with {0: 1} because the empty prefix has XOR state 0.
• ans accumulates our final answer (count of wonderful substrings)
• st represents the current XOR state (bitmask) for the prefix ending at current position

2. Process each character:

for c in word:
    st ^= 1 << (ord(c) - ord("a"))

For each character c, we update the XOR state by flipping the bit corresponding to that character. The expression 1 << (ord(c) - ord("a")) creates a bitmask with only the bit for character c set to 1. For example:

• 'a' → bit 0 → 0000000001
• 'b' → bit 1 → 0000000010
• 'j' → bit 9 → 1000000000

3. Count wonderful substrings ending at current position:

First, count substrings where all characters appear even times:

ans += cnt[st]

If the current state st matches a previous state, the substring between those two positions has all characters appearing an even number of times (since XORing the same bits results in 0).

Then, count substrings where exactly one character appears odd times:

for i in range(10):
    ans += cnt[st ^ (1 << i)]

We check all 10 possible single-bit differences. st ^ (1 << i) flips the i-th bit of the current state. If this modified state was seen before, the substring between that position and the current position has exactly one character with odd count.

4. Update the frequency map:

cnt[st] += 1

Record that we've seen the current XOR state one more time, so future positions can form wonderful substrings with the current position.

Example walkthrough with "aab":

• Position 0 ('a'): st = 0001, check states 0001 (not seen) and single-bit differences, cnt[0001] = 1
• Position 1 ('a'): st = 0000, check states 0000 (seen once from empty prefix), add 1 to answer, cnt[0000] = 2
• Position 2 ('b'): st = 0010, check states and differences, find matches, update count

The algorithm efficiently counts all wonderful substrings in O(n × 10) time, where n is the length of the string.

Example Walkthrough

Let's trace through the algorithm with the string "aba":

Initial State:

• cnt = {0: 1} (empty prefix has XOR state 0)
• ans = 0, st = 0 (represented as 10-bit: 0000000000)

Position 0: character 'a'

• Update state: st = 0 ^ (1 << 0) = 0001 (bit 0 flipped)
• Count substrings ending here:
  • All even counts: cnt[0001] = 0 → add 0
  • One odd count: Check 0001 ^ (1 << i) for i = 0 to 9
    • When i = 0: 0001 ^ 0001 = 0000, cnt[0000] = 1 → add 1 (substring "a")
    • Other i values: no matches → add 0
• Update: ans = 1, cnt[0001] = 1
• Current cnt = {0: 1, 1: 1}

Position 1: character 'b'

• Update state: st = 0001 ^ (1 << 1) = 0011 (bits 0 and 1 set)
• Count substrings ending here:
  • All even counts: cnt[0011] = 0 → add 0
  • One odd count: Check 0011 ^ (1 << i) for i = 0 to 9
    • When i = 0: 0011 ^ 0001 = 0010, cnt[0010] = 0 → add 0
    • When i = 1: 0011 ^ 0010 = 0001, cnt[0001] = 1 → add 1 (substring "ab")
    • Other i values: no matches → add 0
• Update: ans = 2, cnt[0011] = 1
• Current cnt = {0: 1, 1: 1, 3: 1}

Position 2: character 'a'

• Update state: st = 0011 ^ (1 << 0) = 0010 (only bit 1 set now)
• Count substrings ending here:
  • All even counts: cnt[0010] = 0 → add 0
  • One odd count: Check 0010 ^ (1 << i) for i = 0 to 9
    • When i = 0: 0010 ^ 0001 = 0011, cnt[0011] = 1 → add 1 (substring "ba")
    • When i = 1: 0010 ^ 0010 = 0000, cnt[0000] = 1 → add 1 (substring "aba")
    • Other i values: no matches → add 0
• Update: ans = 4, cnt[0010] = 1

Final Answer: 4

The wonderful substrings are:

1. "a" (position 0) - one 'a' (odd)
2. "ab" (positions 0-1) - one 'a' and one 'b' (both odd, but exactly one character type)
3. "ba" (positions 1-2) - one 'b' and one 'a' (both odd, but exactly one character type)
4. "aba" (positions 0-2) - two 'a's (even) and one 'b' (odd)

Note: In the actual count, each single character is wonderful (appears once, which is odd), and "aba" is wonderful because 'a' appears twice (even) and 'b' appears once (odd), meeting our "at most one odd" criterion.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * k) where n is the length of the input string and k = 10 (the number of lowercase letters from 'a' to 'j').

• The outer loop iterates through each character in the word, which takes O(n) time.
• For each character, we:
  • Update the state st with XOR operation: O(1)
  • Look up and add cnt[st]: O(1)
  • Iterate through 10 possible single-bit flips (for loop from 0 to 9): O(10) = O(k)
    • Each iteration performs a lookup in the counter: O(1)
  • Update the counter: O(1)
• Total time per character: O(1) + O(1) + O(k) + O(1) = O(k)
• Overall time complexity: O(n) * O(k) = O(n * k) = O(10n) = O(n)

Space Complexity: O(2^k) where k = 10.

• The cnt Counter stores different bitmask states that represent parity of character frequencies.
• Since we're only dealing with characters 'a' to 'j' (10 characters), each state is represented by a 10-bit number.
• In the worst case, we could have up to 2^10 = 1024 different states stored in the Counter.
• Each state uses O(1) space.
• Total space complexity: O(2^10) = O(1024) = O(1) (constant space relative to input size, but exponential in the alphabet size k)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Initialize the Counter with {0: 1}

A critical pitfall is initializing the counter as empty (Counter()) instead of Counter({0: 1}). This causes the algorithm to miss all wonderful substrings that start from the beginning of the string.

Why this matters: The state 0 represents an empty prefix where no characters have been seen yet. When we encounter a state later that matches 0, it means all characters in that prefix appear an even number of times, making it a wonderful substring.

Incorrect:

bitmask_count = Counter()  # Wrong! Misses substrings from index 0

Correct:

bitmask_count = Counter({0: 1})  # Correct initialization

2. Incorrect Bit Position Calculation

Another common mistake is using the wrong formula to calculate bit positions, especially when dealing with character-to-bit mapping.

Incorrect approaches:

# Wrong: Using 'A' instead of 'a'
char_bit = ord(char) - ord('A')  

# Wrong: Direct character value
char_bit = ord(char)  

# Wrong: Off-by-one error
char_bit = ord(char) - ord('a') + 1

Correct:

char_bit = ord(char) - ord('a')  # Maps 'a'->0, 'b'->1, ..., 'j'->9

3. Checking Wrong Range for Single-Bit Differences

Since the problem specifies only the first 10 lowercase letters ('a' through 'j'), we need to check exactly 10 bit positions. Using the wrong range leads to either missing valid substrings or unnecessary computation.

Incorrect:

# Wrong: Checking all 26 letters
for bit_position in range(26):
    target_bitmask = current_bitmask ^ (1 << bit_position)
    total_wonderful += bitmask_count[target_bitmask]

# Wrong: Off-by-one error
for bit_position in range(9):  # Only checks 'a' through 'i'
    ...

Correct:

for bit_position in range(10):  # Checks exactly 'a' through 'j'
    target_bitmask = current_bitmask ^ (1 << bit_position)
    total_wonderful += bitmask_count[target_bitmask]

4. Updating Counter at Wrong Time

The order of operations matters. You must count wonderful substrings ending at the current position BEFORE updating the counter with the current state.

Incorrect:

for char in word:
    current_bitmask ^= (1 << (ord(char) - ord('a')))
  
    # Wrong: Updating counter before counting
    bitmask_count[current_bitmask] += 1
  
    # This would double-count the current position with itself
    total_wonderful += bitmask_count[current_bitmask]
  
    for bit_position in range(10):
        total_wonderful += bitmask_count[current_bitmask ^ (1 << bit_position)]

Correct:

for char in word:
    current_bitmask ^= (1 << (ord(char) - ord('a')))
  
    # Count substrings first
    total_wonderful += bitmask_count[current_bitmask]
    for bit_position in range(10):
        total_wonderful += bitmask_count[current_bitmask ^ (1 << bit_position)]
  
    # Then update counter
    bitmask_count[current_bitmask] += 1

5. Misunderstanding the XOR Property

Some may try to track actual character counts instead of using XOR for parity. This leads to overcomplicated solutions that are harder to implement and less efficient.

Key insight to remember: XOR naturally tracks parity:

• Even number of XORs with the same bit → bit becomes 0
• Odd number of XORs with the same bit → bit becomes 1

This property makes XOR perfect for tracking whether each character appears an odd or even number of times without maintaining actual counts.