Find the Longest Substring Containing Vowels in Even Counts

Medium
739.

Find the Longest Substring Containing Vowels in Even Counts

Find the Longest Substring Containing Vowels in Even Counts is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var findTheLongestSubstring = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Longest Substring Containing Vowels in Even Counts Solution

Find the Longest Substring Containing Vowels in Even Counts solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Longest Substring Containing Vowels in Even Counts is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon, Google and Meta interviews.

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.

Hints for Find the Longest Substring Containing Vowels in Even Counts

  1. Hint 1

    Only the parity of each vowel count matters, which is five bits of state.

  2. Hint 2

    A substring has all-even vowel counts exactly when the parity state at its two ends is the same.

  3. Hint 3

    So record the first index at which each of the 32 states appears and measure the widest repeat.

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

  1. Start with state 0 recorded at index -1, standing for the empty prefix.
  2. Sweep the string, toggling the bit for each vowel encountered.
  3. If the current state has not been seen, record its index; otherwise the candidate length is i - first[state].
  4. 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

Java

public static int findTheLongestSubstring(String s) {
    int[] first = new int[32];
    Arrays.fill(first, -2);
    first[0] = -1;
    int state = 0, best = 0;
    String vowels = "aeiou";
    for (int i = 0; i < s.length(); i++) {
        int idx = vowels.indexOf(s.charAt(i));
        if (idx >= 0) state ^= 1 << idx;
        if (first[state] == -2) first[state] = i;
        else best = Math.max(best, i - first[state]);
    }
    return best;
}

C++

int findTheLongestSubstring(string s) {
    vector<int> first(32, -2);
    first[0] = -1;
    int state = 0, best = 0;
    string vowels = "aeiou";
    for (int i = 0; i < (int) s.size(); i++) {
        size_t idx = vowels.find(s[i]);
        if (idx != string::npos) state ^= 1 << (int) idx;
        if (first[state] == -2) first[state] = i;
        else best = max(best, i - first[state]);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets