Find the Longest Substring Containing Vowels in Even Counts

medium dp bitmask prefix sum string

Problem

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, the number of occurrences of each of the five vowels 'a', 'e', 'i', 'o', and 'u' must be even in the substring.

Inputs = "eleetminicoworoep"

Output13

The substring "leetminicowor" has e=2, i=2, o=2 and a=u=0 — every vowel even. Encode the running parity of the five vowels as a 5-bit mask; a substring has all-even vowels exactly when its two endpoints share the same mask.

def find_the_longest_substring(s):
    first = {0: -1}
    mask, best = 0, 0
    vowels = "aeiou"
    for i, ch in enumerate(s):
        p = vowels.find(ch)
        if p >= 0:
            mask ^= 1 << p
        if mask in first:
            best = max(best, i - first[mask])
        else:
            first[mask] = i
    return best

function findTheLongestSubstring(s) {
  const first = new Map([[0, -1]]);
  let mask = 0, best = 0;
  const vowels = "aeiou";
  for (let i = 0; i < s.length; i++) {
    const p = vowels.indexOf(s[i]);
    if (p >= 0) mask ^= 1 << p;
    if (first.has(mask)) best = Math.max(best, i - first.get(mask));
    else first.set(mask, i);
  }
  return best;
}

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

int findTheLongestSubstring(string s) {
    vector<int> first(32, -2);
    first[0] = -1;
    int mask = 0, best = 0;
    string vowels = "aeiou";
    for (int i = 0; i < (int)s.size(); i++) {
        int p = vowels.find(s[i]);
        if (p != (int)string::npos) mask ^= 1 << p;
        if (first[mask] != -2) best = max(best, i - first[mask]);
        else first[mask] = i;
    }
    return best;
}

Explanation

A substring is valid when every vowel appears an even number of times. We do not need the exact counts — only the parity (odd or even) of each of the five vowels. So we pack those five parities into a single 5-bit mask: bit 0 for 'a', bit 1 for 'e', and so on.

As we walk the string we keep a running mask of the parities for the whole prefix ending at the current index. Every time we hit a vowel we flip its bit with XOR (mask ^= 1 << p); consonants leave the mask unchanged.

The key observation: the parities inside the substring (j, i] equal prefixMask[i] XOR prefixMask[j]. That XOR is 0 — all vowels even — exactly when prefixMask[i] == prefixMask[j]. So two prefixes with the same mask bound a valid substring.

To make it longest, for each mask we only care about the earliest index it appeared. We store that first occurrence in first (seeded with mask 0 at index -1 so prefixes that are themselves all-even count). When we revisit a mask, i - first[mask] is a candidate length.

Example: "eleetminicoworoep". By the time the running mask returns to a value seen 13 characters earlier, we capture the substring "leetminicowor" with e, i, o each appearing twice, giving the answer 13.

Time: O(n) Space: O(1) (at most 32 masks)