Find the Longest Substring Containing Vowels in Even Counts — Medium Problem & Solution

Return the length of the longest substring of s in which each of the five vowels a, e, i, o and u appears an even number of times. Zero counts as even.

Difficulty: Medium
Topics: Strings, Hash Table, Bit Manipulation, Prefix Sum
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the length of the longest substring of s in which each of the five vowels a, e, i, o and u appears an even number of times. Zero counts as even.

Example 1

Input: s = "eleetminicoworoep"
Output: 13
Explanation: "leetminicowor" has two e's, two o's and two i's.

Example 2

Input: s = "leetcodeisgreat"
Output: 5
Explanation: "leetc" has two e's and no other vowel.

Example 3

Input: s = "bcbcbc"
Output: 6
Explanation: No vowels at all, so the whole string qualifies.

Constraints

1 <= s.length <= 100000
s consists of lowercase English letters.

How to solve Find the Longest Substring Containing Vowels in Even Counts

Track a 5-bit parity mask over the vowels. Two positions with the same mask bracket a substring where every vowel appeared an even number of times, so the answer is the widest gap between equal masks.

Approach

Start with state 0 recorded at index -1, standing for the empty prefix.
Sweep the string, toggling the bit for each vowel encountered.
If the current state has not been seen, record its index; otherwise the candidate length is i - first[state].
Return the largest candidate.

Why it works

The parity mask is the XOR of the vowel indicators seen so far. Equal masks at positions i < j mean every vowel toggled an even number of times in between. Keeping only the first occurrence of each state maximises the distance, and seeding state 0 at -1 lets the answer start at index 0.

Complexity

Time — O(n)
Space — O(32)

Pitfalls

Overwriting the stored index gives the shortest such substring, not the longest.
Forgetting the -1 seed misses substrings that begin at the start of the string.
Non-vowel characters leave the state untouched, which is what makes an all-consonant string fully qualify.

Reference solution

Python

def findTheLongestSubstring(s: str) -> int:
    first = {0: -1}
    state = 0
    best = 0
    for i, c in enumerate(s):
        idx = "aeiou".find(c)
        if idx >= 0:
            state ^= 1 << idx
        if state in first:
            best = max(best, i - first[state])
        else:
            first[state] = i
    return best

JavaScript

var findTheLongestSubstring = function(s) {
    var first = {};
    first["0"] = -1;
    var state = 0, best = 0;
    for (var i = 0; i < s.length; i++) {
        var idx = "aeiou".indexOf(s.charAt(i));
        if (idx >= 0) state ^= 1 << idx;
        var key = String(state);
        if (first[key] === undefined) first[key] = i;
        else if (i - first[key] > best) best = i - first[key];
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue