Number of Wonderful Substrings

Number of Wonderful Substrings

What is this problem about?

The Number of Wonderful Substrings problem asks you to count substrings where at most one character has an odd frequency. The string contains only 'a' to 'j' (10 characters). This coding problem uses XOR-based prefix bitmask to check character frequency parities in O(1) per substring. The hash table, string, bit manipulation, and prefix sum interview pattern is directly demonstrated.

Why is this asked in interviews?

DE Shaw, Meta, Amazon, Google, and Bloomberg ask this because it requires mapping character frequency parities to bitmask states. A substring has at most one odd-frequency character iff the XOR of its prefix bitmasks has exactly 0 or 1 set bit. The prefix XOR hash map technique is the key insight.

Algorithmic pattern used

XOR prefix mask + hash map. Encode each prefix as a 10-bit mask where bit i is the parity of character 'a'+i. For each prefix mask m, count substrings ending here with wonderful property: add freq[m] (both same = all even) + sum of freq[m ^ (1<<i)] for i=0..9 (exactly one bit different = one character odd). Update the frequency map.

Example explanation

s="aabb". Prefix masks: ""=0b00, "a"=0b01, "aa"=0b00, "aab"=0b10, "aabb"=0b00.

• At prefix "a" (mask=1): add freq[1]=0, freq[1^1]=freq[0]=1. Count+=1.
• At prefix "aa" (mask=0): add freq[0]=1, freq[0^1]=freq[1]=1, etc. Count+=1+... Total wonderful substrings = 9 (all substrings with at most 1 odd frequency char).

Common mistakes candidates make

• Checking each substring's character frequencies individually (O(n²)).
• Not initializing frequency map with {0:1} for the empty prefix.
• Off-by-one in which bits correspond to which characters.
• Forgetting to check all 10 single-bit variants (not just 8 or 4).

Interview preparation tip

"Substrings with at most k characters having odd frequency" maps to XOR prefix bitmasks. For k=0: count equal prefix pairs. For k=1: count pairs differing by exactly 1 bit. The hash map approach is O(n * 10) = O(n). Practice this technique on similar problems: "substrings with all even character frequencies" (k=0) and "substrings with at most 1 distinct character having odd count" — they all use the same XOR prefix mask framework.