Problem Description

Given a string s consisting only of lowercase English letters, find the length of the longest substring where each of the vowels ('a', 'e', 'i', 'o', 'u') appears an even number of times (including zero times).

• You may assume s contains only lowercase letters.
• The substring must be contiguous.
• Return the length of the longest such substring.

Thought Process

At first glance, you might think of checking every possible substring and counting the vowels, but this brute-force approach would be too slow for large strings. Instead, we need a way to efficiently track the counts of each vowel as we scan through the string.

The key insight is that the parity (even or odd) of the count for each vowel is all that matters, not the actual count. If we can represent the state of vowel parities at each position, we can quickly check if a substring has all vowels in even counts by comparing states.

This leads to the idea of using a bitmask to encode the even/odd status of each vowel. We can then use a hash map to record the first occurrence of each state, allowing us to find the longest substring with matching start and end states in O(1) time per character.

Solution Approach

Here’s a step-by-step breakdown of the optimized solution:

1. Represent State with Bitmask:
   • Assign a bit (0 or 1) for each vowel: a, e, i, o, u.
   • For example, if a and i have appeared an odd number of times, the bitmask is 10100 (in binary).
2. Use a Hash Map to Track First Occurrences:
   • Map each state (bitmask) to the earliest index where it appears.
   • If the same state appears again at a later index, the substring between these indices has all vowels in even counts.
3. Iterate Through the String:
   • Start with state 0 (all vowels even, before the string).
   • For each character, update the state if it’s a vowel (toggle the corresponding bit).
   • If the current state has been seen before, update the maximum length using the distance between the current and first occurrence indices.
   • If not, record the current index as the first occurrence of this state.
4. Return the Maximum Length Found

This approach ensures that we only need a single pass through the string, with O(1) work per character.

Example Walkthrough

Let's use the input s = "eleetminicoworoep".

1. Start with state = 0 (all vowels even). Record that state 0 first appears at index -1.
2. As we scan each character:
   • At index 0, 'e': toggle bit for 'e' (state becomes 00010). Record first occurrence at index 0.
   • At index 1, 'l': not a vowel, state unchanged.
   • At index 2, 'e': toggle bit for 'e' (state back to 00000). State 0 seen before at index -1, so substring length is 2 - (-1) = 3.
   • Continue updating state and checking/recording first occurrence for each state.
   • At index 14, state 00000 is seen again. The distance from the first occurrence is 14 - (-1) = 15, which is the maximum length.
3. The longest substring with all vowels even is from index 0 to 14, length 15.

Time and Space Complexity

• Brute-force Approach:
  • Time: O(N² * 5) — for each substring, count vowels.
  • Space: O(1) — just for counters.
• Optimized Bitmask Approach:
  • Time: O(N) — single pass through the string.
  • Space: O(32) = O(1) — at most 2⁵ possible states (for 5 vowels), so the hash map is small and constant-sized.

Summary

By representing the parity of vowel counts as a bitmask and tracking their first occurrences, we can efficiently find the longest substring where all vowels appear an even number of times. The approach leverages bitwise operations and hash maps for O(1) state updates and lookups, making it both elegant and highly efficient. This problem is a great example of how encoding state and using prefix information can dramatically simplify and speed up substring problems.

Code Implementation

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        vowel_to_bit = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}
        state = 0
        seen = {0: -1}
        max_len = 0
        for i, c in enumerate(s):
            if c in vowel_to_bit:
                state ^= (1 << vowel_to_bit[c])
            if state in seen:
                max_len = max(max_len, i - seen[state])
            else:
                seen[state] = i
        return max_len
      

class Solution {
public:
    int findTheLongestSubstring(string s) {
        unordered_map<int, int> seen;
        seen[0] = -1;
        int state = 0, maxLen = 0;
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (c == 'a') state ^= (1 << 0);
            else if (c == 'e') state ^= (1 << 1);
            else if (c == 'i') state ^= (1 << 2);
            else if (c == 'o') state ^= (1 << 3);
            else if (c == 'u') state ^= (1 << 4);
            if (seen.count(state)) {
                maxLen = max(maxLen, i - seen[state]);
            } else {
                seen[state] = i;
            }
        }
        return maxLen;
    }
};
      

class Solution {
    public int findTheLongestSubstring(String s) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, -1);
        int state = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'a') state ^= (1 << 0);
            else if (c == 'e') state ^= (1 << 1);
            else if (c == 'i') state ^= (1 << 2);
            else if (c == 'o') state ^= (1 << 3);
            else if (c == 'u') state ^= (1 << 4);
            if (seen.containsKey(state)) {
                maxLen = Math.max(maxLen, i - seen.get(state));
            } else {
                seen.put(state, i);
            }
        }
        return maxLen;
    }
}
      

var findTheLongestSubstring = function(s) {
    const vowelToBit = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4};
    let state = 0;
    let seen = {0: -1};
    let maxLen = 0;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (vowelToBit.hasOwnProperty(c)) {
            state ^= (1 << vowelToBit[c]);
        }
        if (seen.hasOwnProperty(state)) {
            maxLen = Math.max(maxLen, i - seen[state]);
        } else {
            seen[state] = i;
        }
    }
    return maxLen;
};