Find the Longest Substring Containing Vowels in Even Counts - Solution & Explanation
Problem Statement
Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.
Example 1:
Input: s = "eleetminicoworoep" Output: 13 Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.
Example 2:
Input: s = "leetcodeisgreat" Output: 5 Explanation: The longest substring is "leetc" which contains two e's.
Example 3:
Input: s = "bcbcbc" Output: 6 Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.
Constraints:
1 <= s.length <= 5 x 10^5scontains only lowercase English letters.
Approach Overview
Problem Overview: Given a string s, return the length of the longest substring where each vowel (a, e, i, o, u) appears an even number of times. Consonants do not affect the condition. The challenge is detecting when a substring keeps the parity (even/odd count) of all vowels balanced.
Approach 1: Bitmask to Track Vowel Counts (O(n) time, O(1) space)
This approach uses a 5-bit mask to represent the parity of each vowel. Each bit corresponds to one vowel (a,e,i,o,u). When you encounter a vowel while iterating through the string, flip its corresponding bit using XOR. If two prefixes share the same mask, the substring between them has even counts for every vowel because their parity cancels out. Store the earliest index for each mask in a hash map. When the same mask appears again, compute the substring length and update the maximum.
The key insight: there are only 2^5 = 32 possible vowel parity states, so the state space is tiny. This allows constant-space tracking while scanning the string once. This technique combines ideas from bit manipulation and hash table lookups to achieve linear time.
Approach 2: Prefix Parity Tracking (O(n) time, O(1) space)
This method models the problem as prefix parity states. Maintain a prefix representation where each vowel toggles between even and odd counts. The parity state after index i describes the vowel balance from the start to that position. When two indices share the same parity state, the substring between them must contain even counts for all vowels.
During iteration, compute the current state and check whether it appeared before. If it did, update the maximum substring length. If not, record the index as the first occurrence of that state. This technique resembles prefix difference logic used in prefix sum problems, except instead of numeric sums you track parity states.
Both approaches rely on the same parity observation but frame it slightly differently. The bitmask version is more explicit and efficient in implementation, especially in languages where bitwise operations are cheap.
Recommended for interviews: The bitmask parity approach is the expected solution. Interviewers want to see recognition that vowel counts only matter modulo 2 and that a 5-bit mask can encode all states. A brute-force substring check demonstrates understanding but runs in O(n^2). Using a mask with earliest-index tracking reduces the complexity to O(n) and shows strong familiarity with prefix-state problems.
Approach 1: Using Bitmask to Track Vowel Counts
This approach uses a bitmask to represent the parity (even or odd) of each vowel count. We traverse the string, updating the bitmask each time we encounter a vowel. The key observation is that if two prefixes have the same bitmask state, the substring between them has an even count of vowels.
The solution uses a bitmask to track vowel occurrences. The mask changes its state whenever a vowel is encountered. The state array tracks the first occurrence of each bitmask which is crucial for recognizing repeating patterns producing even counts thus finding the longest substring.
Complexity
Time Complexity: O(n), as we traverse through the string once.
Space Complexity: O(1), only a constant space for the state array of size 32 (2^5).
Approach 2: Using Prefix Parity Tracking
In this approach, we will track the parity (even or odd) of the number of occurrences of the vowels using prefix arrays. By storing these in prefix counts we can determine substrings where all vowel counts are even.
In this solution, we use an array to store the first time a specific parity configuration is encountered. This allows the efficient calculation of possible substrings at each step.
Complexity
Time Complexity: O(n), where n is the length of the string, as we iterate over it.
Space Complexity: O(1), by using a fixed-size array to store the first occurrence of each state.
Approach 3: Prefix XOR + Array or Hash Table
According to the problem description, if we use a number to represent the parity of the occurrences of each vowel in a prefix of the string s, then when two prefixes have the same number, the substring between these two prefixes is a valid substring.
We can use the lower five bits of a binary number to represent the parity of the five vowels, where the i-th bit being 1 means the vowel appears an odd number of times in the substring, and 0 means it appears an even number of times.
We use mask to represent this binary number and use an array or hash table d to record the first occurrence of each mask. Initially, we set d[0] = -1, indicating that the start position of the empty string is -1.
We traverse the string s, and if we encounter a vowel, we toggle the corresponding bit in mask. Next, we check if mask has appeared before. If it has, we have found a valid substring, and its length is the current position minus the last occurrence of mask. Otherwise, we store the current position of mask in d.
After traversing the string, we will have found the longest valid substring.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Bitmask to Track Vowel Counts | Time Complexity: O(n), as we traverse through the string once. |
| Using Prefix Parity Tracking | Time Complexity: O(n), where n is the length of the string, as we iterate over it. |
| Prefix XOR + Array or Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmask to Track Vowel Counts | O(n) | O(1) | Optimal solution for interviews and production. Efficient parity tracking with only 32 states. |
| Prefix Parity Tracking | O(n) | O(1) | Useful when reasoning about prefix states or adapting to similar parity-based substring problems. |
Video Solution
Find the Longest Substring Containing Vowels in Even Counts - Leetcode 1371 - Python • NeetCodeIO • 17,527 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Longest Substring Containing Vowels in Even Counts easy or hard?
Find the Longest Substring Containing Vowels in Even Counts Python/Java solution
How to solve Find the Longest Substring Containing Vowels in Even Counts in O(n)?
What is the best approach for Find the Longest Substring Containing Vowels in Even Counts?
Is Find the Longest Substring Containing Vowels in Even Counts asked at Google/Amazon/Meta?
What data structure is used in Find the Longest Substring Containing Vowels in Even Counts?
What is the time complexity of Find the Longest Substring Containing Vowels in Even Counts?
Ready to solve this problem?
Practice Find the Longest Substring Containing Vowels in Even Counts with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor