LeetCode Problem 1915

Difficulty: 🟡 Medium
Topics: Hash Table, String, Bit Manipulation, Prefix Sum

Solution

LeetCode 1915, Number of Wonderful Substrings

Problem Understanding

The problem asks us to count how many non-empty substrings of a given string are considered "wonderful".

A substring is wonderful if at most one character appears an odd number of times inside that substring. The string only contains characters from 'a' to 'j', which means there are only 10 possible letters involved.

To understand the condition more clearly:

• A substring where every character appears an even number of times is wonderful.
• A substring where exactly one character appears an odd number of times is also wonderful.
• A substring where two or more characters appear an odd number of times is not wonderful.

For example:

• "abba" is wonderful because all characters appear an even number of times.
• "aba" is wonderful because 'b' appears once, which is odd, while 'a' appears twice.
• "ab" is not wonderful because both 'a' and 'b' appear once, so two characters have odd frequency.

The input is a single string word with length up to 10^5. This constraint is extremely important because it immediately rules out expensive substring enumeration approaches. A string of length 10^5 has approximately 5 * 10^9 substrings, which is far too many to process directly.

The restriction to only 10 distinct characters is the key observation that enables an efficient solution. Since each character can only have odd or even frequency, we can represent the parity state of all characters using a 10-bit bitmask.

Some important edge cases include:

• A single-character string, every single character substring is wonderful.
• Strings where all characters are identical, almost every substring becomes wonderful because only one character can be odd.
• Strings with many alternating characters, which may frequently create multiple odd counts.
• Very long strings, where efficiency becomes critical.
• Substrings where all counts are even, which must also be counted correctly.

Approaches

Brute Force Approach

The most straightforward approach is to generate every possible substring and check whether it is wonderful.

For each substring, we can count the frequency of all characters and determine how many characters appear an odd number of times. If the number of odd counts is at most one, we increment the answer.

This approach is correct because it directly follows the problem definition. Every substring is examined exactly once, and every substring is validated accurately.

However, the performance is far too slow for the constraints. There are O(n^2) substrings, and checking each substring requires additional work to count frequencies. Even with prefix frequency optimization, the total complexity remains too large for n = 10^5.

Optimal Approach

The key insight is that we only care about whether each character count is odd or even, not the exact count itself.

Parity can be represented using a bitmask:

• Bit 0 represents character 'a'
• Bit 1 represents character 'b'
• ...
• Bit 9 represents character 'j'

If a bit is:

• 0, the character count is even
• 1, the character count is odd

As we scan the string from left to right, we maintain a prefix parity mask.

Suppose:

• prefixMask[i] represents the parity state up to index i
• prefixMask[j] represents the parity state up to index j

Then the substring between them has parity:

prefixMask[i] XOR prefixMask[j]

A substring is wonderful if this XOR result contains:

• zero set bits, meaning all counts are even
• exactly one set bit, meaning exactly one odd count exists

Therefore, for every current mask, we need to count:

• previous identical masks
• previous masks differing by exactly one bit

This transforms the problem into an efficient prefix-state counting problem using a hash map or frequency array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × 10)	O(10)	Enumerates all substrings and checks odd counts
Optimal	O(n × 10)	O(2¹⁰)	Uses prefix parity bitmask and frequency counting

Algorithm Walkthrough

1. Initialize a frequency map to count how many times each parity mask has appeared.

Initially, mask 0 has appeared once because before processing any characters, all counts are even. 2. Maintain a variable called current_mask.

This 10-bit integer stores the parity state of the current prefix. 3. Iterate through the string one character at a time.

For each character:

• Determine which bit corresponds to that character.
• Flip that bit using XOR.

For example:

current_mask ^= (1 << char_index)

If the bit was 0, it becomes 1.

If it was 1, it becomes 0. 4. Count substrings where all character counts are even.

If a previous prefix had the exact same mask, then the substring between them has parity 0.

Add:

frequency[current_mask]

to the answer. 5. Count substrings where exactly one character has odd frequency.

We try flipping each of the 10 bits individually:

candidate_mask = current_mask ^ (1 << bit)

If this candidate mask appeared before, then the substring between those prefixes differs by exactly one odd character.

Add all such frequencies to the answer. 6. After counting valid substrings ending at the current position, record the current mask in the frequency map. 7. Continue until the entire string has been processed. 8. Return the accumulated answer.

Why it works

The algorithm relies on the property that XOR between two prefix parity masks gives the parity state of the substring between them.

A substring is wonderful if its parity mask contains at most one set bit. Therefore:

• identical masks produce zero odd counts
• masks differing by one bit produce exactly one odd count

By counting previously seen masks efficiently, we can determine the number of valid substrings ending at each position in constant time.

Python Solution

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        mask_frequency = {0: 1}
        
        current_mask = 0
        wonderful_count = 0
        
        for char in word:
            bit_index = ord(char) - ord('a')
            
            current_mask ^= (1 << bit_index)
            
            # Case 1: all character counts are even
            wonderful_count += mask_frequency.get(current_mask, 0)
            
            # Case 2: exactly one character count is odd
            for bit in range(10):
                candidate_mask = current_mask ^ (1 << bit)
                wonderful_count += mask_frequency.get(candidate_mask, 0)
            
            mask_frequency[current_mask] = (
                mask_frequency.get(current_mask, 0) + 1
            )
        
        return wonderful_count

The implementation closely follows the algorithm described earlier.

The dictionary mask_frequency stores how many times each prefix parity mask has appeared. The entry {0: 1} is important because it represents the empty prefix before processing any characters.

The variable current_mask tracks the parity of character frequencies up to the current position. Each character flips its corresponding bit using XOR.

After updating the mask, the code first counts substrings where all character counts are even. This happens when the current mask matches a previously seen mask.

Next, the code checks all masks differing by exactly one bit. These correspond to substrings where exactly one character has odd frequency.

Finally, the current mask is added to the frequency map so future substrings can use it.

Because there are only 10 bits, the inner loop always runs exactly 10 times, making the algorithm highly efficient.

Go Solution

func wonderfulSubstrings(word string) int64 {
	maskFrequency := make([]int64, 1<<10)

	maskFrequency[0] = 1

	currentMask := 0
	var wonderfulCount int64 = 0

	for _, char := range word {
		bitIndex := int(char - 'a')

		currentMask ^= (1 << bitIndex)

		// Case 1: all counts are even
		wonderfulCount += maskFrequency[currentMask]

		// Case 2: exactly one odd count
		for bit := 0; bit < 10; bit++ {
			candidateMask := currentMask ^ (1 << bit)
			wonderfulCount += maskFrequency[candidateMask]
		}

		maskFrequency[currentMask]++
	}

	return wonderfulCount
}

The Go implementation uses a fixed-size slice instead of a hash map because there are only 2^10 = 1024 possible masks. This is both faster and more memory efficient.

The answer is stored as int64 because the number of substrings can exceed the range of a standard 32-bit integer.

Other than these language-specific details, the logic is identical to the Python implementation.

Worked Examples

Example 1

Input:

word = "aba"

Initial state:

current_mask = 0000000000
frequency[0] = 1
answer = 0

Step	Character	Mask After Update	Matching Masks	Added Count	Total
1	a	0000000001	flip bit 0 gives 0	1	1
2	b	0000000011	flip bit 1 gives 1	1	2
3	a	0000000010	flip bit 0 gives 3, flip bit 1 gives 0	2	4

Final answer:

4

Wonderful substrings:

"a", "b", "a", "aba"

Example 2

Input:

word = "aabb"

Step	Character	Current Mask	New Wonderful Substrings	Running Total
1	a	1	"a"	1
2	a	0	"aa", "a"	3
3	b	2	"b", "aab"	5
4	b	0	"bb", "abb", "aabb", "b"	9

Final answer:

9

Example 3

Input:

word = "he"

Step	Character	Current Mask	Wonderful Substrings	Total
1	h	10000000	"h"	1
2	e	10010000	"e"	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × 10)	Each character checks 10 possible bit flips
Space	O(2¹⁰)	At most 1024 distinct parity masks

The algorithm processes each character exactly once. For every character, it performs a constant amount of work plus a loop over 10 bits.

Since the alphabet size is fixed at 10, the complexity simplifies to linear time, O(n).

The space complexity is also effectively constant because there are only 1024 possible masks regardless of input size.

Test Cases

solution = Solution()

# Provided examples
assert solution.wonderfulSubstrings("aba") == 4  # basic mixed example
assert solution.wonderfulSubstrings("aabb") == 9  # multiple wonderful substrings
assert solution.wonderfulSubstrings("he") == 2  # different characters only

# Single character
assert solution.wonderfulSubstrings("a") == 1  # smallest valid input

# All same character
assert solution.wonderfulSubstrings("aaaa") == 10  # every substring is wonderful

# No multi-character wonderful substrings
assert solution.wonderfulSubstrings("ab") == 2  # only single letters work

# Alternating pattern
assert solution.wonderfulSubstrings("abab") == 7  # mixed parity transitions

# All unique characters
assert solution.wonderfulSubstrings("abcdefghij") == 10  # only single chars

# Even frequency full string
assert solution.wonderfulSubstrings("aabbcc") == 16  # many even-count substrings

# Long repeated pattern
assert solution.wonderfulSubstrings("jjjjj") == 15  # all substrings valid

# Mixed parity stress case
assert solution.wonderfulSubstrings("abcabc") == 9  # repeated parity states

Test	Why
"aba"	Verifies standard mixed behavior
"aabb"	Tests multiple overlapping wonderful substrings
"he"	Ensures only single characters count
"a"	Smallest valid input
"aaaa"	Every substring should be wonderful
"ab"	Tests rejection of two odd counts
"abab"	Verifies repeated parity transitions
"abcdefghij"	Tests many distinct characters
"aabbcc"	Tests even-frequency substrings
"jjjjj"	Tests repeated final alphabet character
"abcabc"	Stress test for repeated mask reuse

Edge Cases

One important edge case is a single-character string. Every single character substring is automatically wonderful because only one character appears once. A buggy implementation might forget to initialize the empty prefix mask frequency correctly, causing these substrings to be missed. The initialization frequency[0] = 1 ensures such cases are handled properly.

Another important case is when all characters are identical, such as "aaaaa". In this situation, every substring is wonderful because there can never be more than one character with odd frequency. The parity mask repeatedly alternates between two states, and the algorithm efficiently counts all matching prefixes without enumerating substrings explicitly.

A more subtle edge case occurs when multiple characters have odd frequencies simultaneously. For example, "ab" should not count as wonderful because both characters appear once. The algorithm handles this correctly because it only accepts masks with zero differing bits or exactly one differing bit. Any substring producing two or more differing bits is automatically excluded.

A final important edge case involves very long inputs near the constraint limit. A brute-force approach would time out because the number of substrings grows quadratically. The bitmask prefix technique ensures the solution remains efficient even for strings of length 100000.