Solution: Find the Longest Substring Having Vowels in Even Counts

Understand how to find the longest substring in which all vowels appear in even counts by applying bitwise XOR operations. Explore a method that toggles bits for vowels to track their parity while traversing the string. Learn to use prefix XOR states and first occurrence tracking to identify valid substrings efficiently with linear time and constant space complexity.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

Given the string s, return the length of the longest substringA substring is a consecutive sequence of characters within a string. in which each vowel—a, e, i, o, and u—appears an even number of times.

Constraints:

$1 \leq$ s.length $\leq 5 \times 10^3$
s contains only lowercase English letters.

Solution

It’s important to note that we only need to know whether each vowel appears an even or odd number of times in any substring—we don’t need the exact counts. This is where bitwise operations can help. In bitwise terms, we use XOR on its bits to check if a value occurs an even or odd number of times (its parity). If the result of XOR is 1, the value has occurred an odd number of times; if it’s 0, it’s even. We’ll apply this idea to the characters in the input string: each vowel is represented by a bit, and as we process each character, we’ll use XOR with a fixed-size bitmask to track whether it has an even or odd count.

Each vowel is assigned a unique bit in a ...