Find the Longest Substring Containing Vowels in Even Counts

Find the Longest Substring Containing Vowels in Even Counts

What is this problem about?

The Find the Longest Substring Containing Vowels in Even Counts interview question asks you to find the length of the longest substring where each of the five English vowels ('a', 'e', 'i', 'o', 'u') appears an even number of times (0 is considered even). Consonants can appear any number of times.

Why is this asked in interviews?

This is a high-signal problem for companies like Microsoft, Meta, and Google. It tests your ability to combine Bit Manipulation with the Prefix Sum interview pattern. It evaluation whether you can represent the parity (even/odd) of multiple items as a single integer state (a bitmask) and use a Hash Map to find the earliest occurrence of that state to maximize the distance.

Algorithmic pattern used

This problem uses a Bitmask Prefix State approach.

1. Represent the state of the 5 vowels as a 5-bit integer. Each bit is 1 if the vowel has appeared an odd number of times, and 0 if even.
2. Initialize a map firstOccurrence where mask 0 is at index -1.
3. Iterate through the string. If the character is a vowel, flip its corresponding bit in the currentMask (using XOR).
4. If currentMask has been seen before, the substring between the firstOccurrence[currentMask] and the current index has an even count of all vowels (because $Odd - Odd = Even$ and $Even - Even = Even$).
5. The length is currentIndex - firstOccurrence[currentMask].

Example explanation

String: "eleetminicoworoep"

1. 'e': mask becomes 00010. firstOccurrence[00010] = 0.
2. 'l': no change.
3. 'e': mask becomes 00000 (bit flipped back).
4. mask 0 was at -1. Length = $1 - (-1) = 2$ ("el").
5. ... continue ...
6. Whenever the bits are all 0, or match a previous state, a valid substring is found.

Common mistakes candidates make

• Using an array of 5 counts: This makes the state complex to track in a map. A bitmask is much more efficient.
• Consonant handling: Forgetting that consonants don't change the parity mask.
• Initialization: Failing to put mask 0 at index -1, which misses valid substrings that start from the beginning of the string.

Interview preparation tip

Bitmasks are perfect for tracking "parity" or "existence" of a small set of items (like 5 vowels or 26 letters). Combining bitmasks with a Hash Map to store the "first seen" index is a classic Prefix Sum interview pattern for finding the longest subarray with a specific property.