Find the Longest Substring Containing Vowels in Even Counts - Video Solutions

Problem Overview: Given a string s, return the length of the longest substring where each vowel (a, e, i, o, u) appears an even number of times. Consonants do not affect the condition. The challenge is detecting when a substring keeps the parity (even/odd count) of all vowels balanced.

Approach 1: Bitmask to Track Vowel Counts (O(n) time, O(1) space)

This approach uses a 5-bit mask to represent the parity of each vowel. Each bit corresponds to one vowel (a,e,i,o,u). When you encounter a vowel while iterating through the string, flip its corresponding bit using XOR. If two prefixes share the same mask, the substring between them has even counts for every vowel because their parity cancels out. Store the earliest index for each mask in a hash map. When the same mask appears again, compute the substring length and update the maximum.

The key insight: there are only 2^5 = 32 possible vowel parity states, so the state space is tiny. This allows constant-space tracking while scanning the string once. This technique combines ideas from bit manipulation and hash table lookups to achieve linear time.

Approach 2: Prefix Parity Tracking (O(n) time, O(1) space)

This method models the problem as prefix parity states. Maintain a prefix representation where each vowel toggles between even and odd counts. The parity state after index i describes the vowel balance from the start to that position. When two indices share the same parity state, the substring between them must contain even counts for all vowels.

During iteration, compute the current state and check whether it appeared before. If it did, update the maximum substring length. If not, record the index as the first occurrence of that state. This technique resembles prefix difference logic used in prefix sum problems, except instead of numeric sums you track parity states.

Both approaches rely on the same parity observation but frame it slightly differently. The bitmask version is more explicit and efficient in implementation, especially in languages where bitwise operations are cheap.

Recommended for interviews: The bitmask parity approach is the expected solution. Interviewers want to see recognition that vowel counts only matter modulo 2 and that a 5-bit mask can encode all states. A brute-force substring check demonstrates understanding but runs in O(n^2). Using a mask with earliest-index tracking reduces the complexity to O(n) and shows strong familiarity with prefix-state problems.