Find the Longest Substring Containing Vowels in Even Counts Solution

Problem

Given a string, find the length of the longest substring where every vowel (a, e, i, o, u) appears an even number of times (zero counts as even). Non-vowel characters are ignored entirely.

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The substring "leetminicoworо" (indices 1–13) contains exactly 2 e's, 2 i's, and 2 o's — all even, no a's or u's.

A counter-example: "leetcode" returns 5 ("leetc" has two e's and zero of everything else). The full string "leetcode" doesn't qualify because o and the final e each appear once (odd).

Intuition

Two positions in the string have the same vowel-parity state when the substring between them has changed each vowel's count by zero or two — meaning each vowel's net contribution is even. So the problem reduces to: find the earliest position that shares the current parity state, then the substring from there to now is the longest valid ending here. Representing all five vowel parities as a 5-bit bitmask and recording the first time each bitmask appears makes this a single linear scan.

Approach 1 — Brute Force

For every possible starting index, scan rightward tracking a parity bitmask per vowel. Whenever all five parities are zero, record the substring length. No extra space needed beyond the running bitmask.

For each starting index start, reset the parity bitmask to 0.
Extend end from start to the end of the string.
If the current character is a vowel, XOR the corresponding bit in the bitmask.
If the bitmask is 0 (all even), update the answer with end - start + 1.
Return the maximum length found.

1def findTheLongestSubstring(s: str) -> int:
2    vowel_bit = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
3    longest = 0
4
5    for start in range(len(s)):
6        parity_mask = 0
7        for end in range(start, len(s)):
8            if s[end] in vowel_bit:
9                parity_mask ^= (1 << vowel_bit[s[end]])  # toggle this vowel's parity
10            if parity_mask == 0:  # all vowels have even counts in s[start..end]
11                longest = max(longest, end - start + 1)
12
13    return longest

Time: O(n²) — every pair of indices is examined once.
Space: O(1) — only the running bitmask and the answer variable.

Approach 2 — Bitmask Prefix + Hash Map

The key observation: if two positions i and j (with i < j) share the same parity bitmask, then the substring s[i+1..j] has all vowels with even counts. So we store the earliest index where each bitmask first appeared, then in a single pass look up the answer for each position.

Initialize a hash map first_seen = {0: -1} — bitmask 0 is "seen" at the virtual index before the string starts.
Scan each character, updating parity_mask by XOR-ing the vowel's bit if the character is a vowel.
If parity_mask is already in first_seen, a valid substring ends here: its length is index - first_seen[parity_mask].
Otherwise, record this as the first time we've seen this bitmask.
Return the maximum length found.

1def findTheLongestSubstring(s: str) -> int:
2    vowel_bit = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
3    # earliest index where each parity bitmask was first seen
4    first_seen = {0: -1}
5    parity_mask = 0
6    longest = 0
7
8    for index, char in enumerate(s):
9        if char in vowel_bit:
10            parity_mask ^= (1 << vowel_bit[char])  # toggle this vowel's parity bit
11
12        if parity_mask in first_seen:
13            # s[first_seen[parity_mask]+1 .. index] has all even vowel counts
14            longest = max(longest, index - first_seen[parity_mask])
15        else:
16            first_seen[parity_mask] = index  # only store the earliest occurrence
17
18    return longest

Time: O(n) — one pass through the string; each character does O(1) work.
Space: O(1) — the hash map holds at most 2⁵ = 32 entries (one per possible bitmask).

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Input is very short (n ≤ 1000)
Bitmask Prefix	O(n)	O(1)	General case — this is always the right answer

Common Mistakes

Overwriting earlier first-seen entries — once a bitmask is recorded in first_seen, never update it. The earliest occurrence gives the longest substring. Overwriting with a later index silently produces a wrong (shorter) answer.
Forgetting the initial {0: -1} entry — without this, a prefix that itself has all-even vowels (e.g., "leetcode" → "leetc") won't be found, because parity_mask == 0 won't exist in the map.
Using character counts instead of parities — you don't need the actual count of each vowel, only whether it's odd or even. Storing full counts uses O(n) space and complicates the logic needlessly.
Thinking space is O(n) — the hash map is bounded by the number of distinct bitmasks, which is 2⁵ = 32 regardless of input length.
Applying a sliding window — this problem looks like a sliding window problem (longest substring with a property), but a shrinking window doesn't work here because removing a character can make a previously-odd count even again. The prefix hash map is the correct structure.

Find the Longest Substring Containing Vowels in Even Counts — Solution