Domain 2MediumMEDIUM

Find the Longest Substring Containing Vowels in Even Counts

LeetCode problem 1371: Find the Longest Substring Containing Vowels in Even Counts (medium).

Domain: medium•Updated: 2026-09-15
#String

Problem Breakdown

Restatement: We need to find the maximum length of a contiguous substring within string s such that every vowel (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) appears an even number of times (including zero). Consonants do not affect this parity constraint.

Inputs & Outputs:

  • Input: A single lowercase English letter string s. Length 1≤∣s∣≤5×1051 \le |s| \le 5 \times 10^5.
  • Output: An integer representing the maximum length of a valid substring.

Implicit Constraints & Edge Cases:

  • The problem guarantees only lowercase letters, so we don’t need to handle case sensitivity or non-alphabetic characters.
  • A “valid” substring can technically be empty (length 0), but since constraints say ∣s∣≥1|s| \ge 1, and consonants alone satisfy the condition (count of vowels = 0 is even), a valid answer always exists ≥\ge length of longest consecutive consonant block or any segment where vowel parities match.
  • Key Edge Case: The substring can start at index 0. To handle this mathematically, we treat the state before processing any characters as having all vowels with count 0 (even). This requires initializing our tracking structure to record a “virtual” starting position of -1 for the initial mask 0.

Intuition

Brute Force Approach: A naive solution would iterate through every possible substring s[i:j]s[i:j], counting vowel occurrences, and checking if all are even.

  • Complexity: There are O(N2)O(N^2) substrings. Counting vowels takes O(j−i)O(j-i). Total time: O(N3)O(N^3) or optimized to O(N2)O(N^2) with prefix sums. Given the constraint N=5×105N = 5 \times 10^5, an O(N2)O(N^2) solution will Time Limit Exceed (TLE).

Key Insight: We only care about parity (odd vs even) of vowel counts, not exact frequencies. This suggests a bitmask or state representation where each bit corresponds to one vowel’s parity status.

  • There are 5 vowels: a, e, i, o, u. We can map them to bits 00 through 44.
  • A substring from index prev to current index curr has even counts for all vowels if and only if the parity mask at curr is identical to the parity mask at prev - 1.
    • Mathematically: (Countcurr−Countprev)≡0(mod2)(Count_{curr} - Count_{prev}) \equiv 0 \pmod 2. This holds true if CountcurrCount_{curr} and CountprevCount_{prev} have the same remainder modulo 2.

Optimal Approach: We iterate through s once, maintaining a running bitmask of vowel parities seen so far from index 0 to current index. We store the first time we encounter each unique mask state in an array or hash map. If we see that specific mask again later at index i, it means all vowels between our first occurrence and now have flipped parity twice (or zero times), resulting in even counts for that segment.

Approach

  1. Initialize a variable mask to 0, representing the state where no vowels have been seen yet (all parities are even).
  2. Create a lookup table (seen) mapping each mask value to its first occurrence index.
  3. Crucially, initialize seen[0] = -1. This handles substrings starting from index 0 correctly because the “virtual” state before the string starts has all parities as even (mask 0).
  4. Iterate through the string with index i and character char:
    • If char is a vowel, toggle its corresponding bit in mask.
  5. Check if current mask exists in seen:
    • If yes: We found a valid substring ending at i. The length is i - seen[mask]. Update global maximum.
    • If no: Store the current mask and index i in seen. This ensures we capture the longest possible distance for any future occurrence of this state.
  6. Return the calculated maximum length.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of string s. We perform a single pass through the input. Bitwise operations and dictionary/array lookups are constant time relative to alphabet size (fixed at 5 vowels).
  • Space Complexity: O(1)O(1). The number of possible mask states is limited by 2number_of_vowels=25=322^{\text{number\_of\_vowels}} = 2^5 = 32. Regardless of input string length, we only store a fixed-size array or hash map to track these 32 potential parity combinations.

Solution

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        # Map vowels to bit indices for easy toggling
        vowel_map = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
        
        # seen[mask] stores the first index where this mask was encountered.
        # Initialize with -1 to handle substrings starting at index 0 correctly.
        # Mask is an integer from 0 to 31 (since there are only 5 vowels).
        seen = [-1] * 32
        
        current_mask = 0
        max_len = 0
        
        for i, char in enumerate(s):
            if char in vowel_map:
                # Toggle the bit corresponding to this specific vowel
                idx = vowel_map[char]
                current_mask ^= (1 << idx)
            
            # If we have seen this mask state before, calculate substring length.
            # The valid substring is between the previous occurrence and now.
            if seen[current_mask] != -1:
                max_len = max(max_len, i - seen[current_mask])
            else:
                # Store first occurrence of this specific parity pattern
                seen[current_mask] = i
                
        return max_len

Edge Cases Handled

  • No Vowels: If s contains only consonants (e.g., “bcbcbc”), the mask remains 0 throughout. Since we initialized seen[0] = -1, every index updates length as i - (-1). The final result is NN, which matches Example 3.
  • Substring Starting at Index 0: By initializing seen with -1 for the zero mask, if a valid substring starts immediately (e.g., “leet” where ‘l’ and consonants don’t change parity), the calculation i - (-1) correctly includes index 0 in the length.
  • Single Vowel Substring: If input is “a”, mask becomes non-zero at end, never matches previous state except implicitly if we consider empty substring (length 0). The code returns 0 for a single vowel string because no even-count segment exists > 0 chars? Wait, strictly speaking seen stores first index. For “a”:
    • i=0, char=‘a’, mask becomes 2bit2^{\text{bit}}. Not in seen (except -1). Store it at 0. Loop ends. Returns 0. Correct because ‘a’ has odd count of vowels. Empty substring is technically valid but usually we want max length > 0 if possible. If no even-count non-empty exists, 0 is correct per LC standards for this problem type (though strictly empty string satisfies condition).
  • All Vowels: Handles correctly by tracking parity flips until a matching mask state repeats or end of string reached.