Number of Wonderful Substrings - Video Solutions

Problem Overview: Given a string consisting of the first ten lowercase letters (a–j), count how many substrings are wonderful. A substring is wonderful when at most one character appears an odd number of times. The task is essentially checking parity of character counts across all substrings efficiently.

Approach 1: Bitmask and Prefix Sum (O(n) time, O(1) space)

The key observation: you only care whether each character count is odd or even. That means you can represent the state of the string using a 10‑bit mask where bit i indicates whether character 'a' + i currently has odd frequency. As you iterate through the string, update this mask using XOR. Each mask represents the parity state of the prefix.

A substring is wonderful if its parity mask has either zero odd characters or exactly one odd character. Using the prefix sum idea, the parity of substring [l..r] equals prefixMask[r] ^ prefixMask[l-1]. To count valid substrings ending at position r, track how many times each mask has appeared using a hash table or array of size 2^10. First add matches where the mask is identical (all even counts). Then flip each of the 10 bits and check those masks to allow exactly one odd character. Each step performs constant work, giving O(n * 10) ≈ O(n) time and O(2^10) space.

This approach relies heavily on bit manipulation. The bitmask compresses parity information into a small integer, making state comparison extremely fast.

Approach 2: Sliding Window (Basic) (O(n^2) time, O(1) space)

A more straightforward idea expands substrings using a sliding window style enumeration. Fix the left boundary and extend the right pointer while tracking frequency counts for the ten characters. After each extension, compute how many characters currently have odd counts. If that number is ≤ 1, the substring is wonderful.

This method uses a small frequency array of size 10 and updates counts as the window expands. Checking the odd-count condition requires scanning the array or maintaining an auxiliary counter. While easy to implement, every starting index may scan many characters, resulting in O(n^2) time in the worst case. Space remains O(1) since the alphabet size is fixed.

Recommended for interviews: The bitmask + prefix frequency approach is what interviewers expect. It reduces the substring parity check to constant-time mask comparisons and demonstrates strong understanding of prefix techniques and parity encoding. The quadratic window approach is useful for reasoning about the problem initially, but the optimized bitmask solution shows the algorithmic insight required for medium-level string problems.