Problem Statement

Find Longest Substring With Even Vowel Counts

You are given a string. A substring is a chunk of letters that sit right next to each other inside that string. The job is to find the longest substring where every vowel (a, e, i, o, u) shows up an even number of times. Even means 0, 2, 4, and so on. So in the winning chunk, the number of a's is even, the number of e's is even, and the same for i, o, and u.

mediumBit ManipulationStringBit ManipulationTime: O(n) · Space: O(1)

Signals to notice

longest substring with all vowels appearing even timesbitmask parity trackingprefix XOR

Brute force first

Check every substring — O(n²).

The key insight

5-bit bitmask tracks vowel parity. Same bitmask at positions i,j means even counts between them. Store first occurrence. O(n).

Trace it on `s="leetcodeisgreat" (answer 5)`

init: mask=00000, firstSeen={0:-1}, best=0
i0 'l': not vowel, mask=00000 seen@-1 -> best=0-(-1)=1
i2 'e': mask 00010->00000, seen@-1 -> best=max(1,2-(-1))=3
i4 'c': mask still 00000, seen@-1 -> best=max(3,4-(-1))=5
i5 'o': mask=01000 NEW -> firstSeen[01000]=5, best=5
i8 'i': mask=01110 NEW -> firstSeen[01110]=8, best=5
i11 'r': mask=01110 seen@8 -> 11-8=3, best stays 5
i14 't': mask=01101 seen@13 -> 14-13=1; loop ends, return best=5

What must stay true

Same bitmask = same parity state = vowels toggled even times between. Length = j - firstOccurrence[mask].

Shape of the loop

mask = 0; firstSeen = {0: -1}; best = 0
for i, ch in s:
    if ch is a vowel: mask ^= (1 << vowelIndex[ch])   # flip that vowel's parity bit
    if mask seen before: best = max(best, i - firstSeen[mask])
    else: firstSeen[mask] = i                          # record earliest index per mask
return best

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not initializing mask 0 at position -1 — needed for substrings starting at index 0.

Bit Manipulation Pattern