Find the Longest Substring Containing Vowels in Even Counts solution and explanation
Google
9 more videos on this problem
Find the Longest Substring Containing Vowels in Even Counts - Leetcode 1371 - PythonNeetCodeIO · 24:01 · 17K views
Find the Longest Substring Containing Vowels in Even Counts | Leetcode 1371 | codestorywithMIKcodestorywithMIK · 29:45 · 16K views
Leetcode Find the Longest Substring Containing Vowels in Even CountsSandip Jana · 18:05 · 6K views
LeetCode 1371. Find the Longest Substring Containing Vowels in Even CountsHappy Coding · 24:26 · 5K views
1371. Find the Longest Substring Containing Vowels in Even Counts | LEETCODE MEDIUM | BITMASKcode Explainer · 11:16 · 5K views
Find the Longest Substring Containing Vowels in Even Counts| Leetcode 1371 | MUST DO bit DSACode Thoughts · 19:51 · 1K views
Leetcode 1371. Find the Longest Substring Containing Vowels in Even CountsCode-Yao · 13:04 · 371 views
LeetCode 1371 - Find the Longest Substring Containing Vowels in Even Counts - JavaAlpha-Code · 15:00 · 298 views
1371 | Find the Longest Substring Containing Vowels in Even Counts | leetcode daily10 Minutes CS · 8:46 · 148 views
Find the Longest Substring Containing Vowels in Even Counts | LeetCode 1371CodeInBits · 10:49 · 127 views
The problem
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.
def findTheLongestSubstring(s: str) -> int:
state = {0: -1} # Initial condition, state 0 starts at index -1
maxLength = mask = 0
for i, char in enumerate(s):
if char == 'a':
mask ^= (1 << 0)
elif char == 'e':
mask ^= (1 << 1)
elif char == 'i':
mask ^= (1 << 2)
elif char == 'o':
mask ^= (1 << 3)
elif char == 'u':
mask ^= (1 << 4)
# Check if mask has been seen before
if mask in state:
maxLength = max(maxLength, i - state[mask])
else:
state[mask] = i
return maxLength
print(findTheLongestSubstring("eleetminicoworoep")) # Output: 13
import java.util.HashMap;
import java.util.Map;
public class LongestSubstringVowelsEven {
public static int findTheLongestSubstring(String s) {
Map<Integer, Integer> stateMap = new HashMap<>();
stateMap.put(0, -1);
int maxLength = 0, mask = 0;
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case 'a': mask ^= (1 << 0); break;
case 'e': mask ^= (1 << 1); break;
case 'i': mask ^= (1 << 2); break;
case 'o': mask ^= (1 << 3); break;
case 'u': mask ^= (1 << 4); break;
}
if (stateMap.containsKey(mask)) {
maxLength = Math.max(maxLength, i - stateMap.get(mask));
} else {
stateMap.put(mask, i);
}
}
return maxLength;
}
public static void main(String[] args) {
System.out.println(findTheLongestSubstring("eleetminicoworoep")); // Output: 13
}
}
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
int findTheLongestSubstring(string s) {
unordered_map<int, int> state;
int maxLength = 0, mask = 0;
state[0] = -1; // Starting condition
for (int i = 0; i < s.length(); ++i) {
if (s[i] == 'a') mask ^= (1 << 0);
else if (s[i] == 'e') mask ^= (1 << 1);
else if (s[i] == 'i') mask ^= (1 << 2);
else if (s[i] == 'o') mask ^= (1 << 3);
else if (s[i] == 'u') mask ^= (1 << 4);
if (state.find(mask) != state.end()) {
maxLength = max(maxLength, i - state[mask]);
} else {
state[mask] = i;
}
}
return maxLength;
}
int main() {
cout << findTheLongestSubstring("eleetminicoworoep") << endl; // Output: 13
return 0;
}
function findTheLongestSubstring(s) {
let state = {0: -1};
let maxLength = 0, mask = 0;
for (let i = 0; i < s.length; i++) {
switch (s[i]) {
case 'a': mask ^= (1 << 0); break;
case 'e': mask ^= (1 << 1); break;
case 'i': mask ^= (1 << 2); break;
case 'o': mask ^= (1 << 3); break;
case 'u': mask ^= (1 << 4); break;
}
if (state.hasOwnProperty(mask)) {
maxLength = Math.max(maxLength, i - state[mask]);
} else {
state[mask] = i;
}
}
return maxLength;
}
console.log(findTheLongestSubstring("eleetminicoworoep")); // Output: 13
#include <stdio.h>
#include <string.h>
int findTheLongestSubstring(char * s){
int n = strlen(s);
int vowelsMask = 0, maxLength = 0;
int state[32];
for (int i = 0; i < 32; i++) {
state[i] = -1; // Initialize all states to -1
}
state[0] = 0; // Bitmask state 0 starts at index 0
for (int i = 0; i < n; i++) {
if (s[i] == 'a') vowelsMask ^= (1 << 0);
else if (s[i] == 'e') vowelsMask ^= (1 << 1);
else if (s[i] == 'i') vowelsMask ^= (1 << 2);
else if (s[i] == 'o') vowelsMask ^= (1 << 3);
else if (s[i] == 'u') vowelsMask ^= (1 << 4);
if (state[vowelsMask] >= 0) {
maxLength = fmax(maxLength, i + 1 - state[vowelsMask]);
} else {
state[vowelsMask] = i + 1;
}
}
return maxLength;
}
int main() {
char s[] = "eleetminicoworoep";
printf("%d\n", findTheLongestSubstring(s)); // Output: 13
return 0;
}
using System;
using System.Collections.Generic;
public class Solution {
public int FindTheLongestSubstring(string s) {
Dictionary<int, int> state = new Dictionary<int, int>();
state[0] = -1;
int maxLength = 0, mask = 0;
for (int i = 0; i < s.Length; i++) {
switch (s[i]) {
case 'a': mask ^= (1 << 0); break;
case 'e': mask ^= (1 << 1); break;
case 'i': mask ^= (1 << 2); break;
case 'o': mask ^= (1 << 3); break;
case 'u': mask ^= (1 << 4); break;
}
if (state.ContainsKey(mask)) {
maxLength = Math.Max(maxLength, i - state[mask]);
} else {
state[mask] = i;
}
}
return maxLength;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.FindTheLongestSubstring("eleetminicoworoep")); // Output: 13
}
}In the Python solution, a dictionary tracks the first occurrence of each bitmask. The bitmask is updated through a simple toggle switch for each vowel, and the length of any consecutive repeated pattern of bitmasks denotes a valid substring.
Time Complexity: O(n), where n is the length of the string, because we traverse it once.
Space Complexity: O(1), and although we use a dictionary, its size is bounded by 32 different bitmasks.
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.
def findTheLongestSubstring(s: str) -> int:
state_map = {0: -1}
mask = 0
maxLength = 0
for i, char in enumerate(s):
if char == 'a':
mask ^= (1 << 0)
elif char == 'e':
mask ^= (1 << 1)
elif char == 'i':
mask ^= (1 << 2)
elif char == 'o':
mask ^= (1 << 3)
elif char == 'u':
mask ^= (1 << 4)
if mask in state_map:
maxLength = max(maxLength, i - state_map[mask])
else:
state_map[mask] = i
return maxLength
print(findTheLongestSubstring("eleetminicoworoep")) # Output: 13
import java.util.HashMap;
import java.util.Map;
public class LongestVowelSubstring {
public int findTheLongestSubstring(String s) {
int state = 0, maxLength = 0;
Map<Integer, Integer> firstOccurrence = new HashMap<>();
firstOccurrence.put(0, -1);
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == 'a') state ^= (1 << 0);
else if (ch == 'e') state ^= (1 << 1);
else if (ch == 'i') state ^= (1 << 2);
else if (ch == 'o') state ^= (1 << 3);
else if (ch == 'u') state ^= (1 << 4);
if (firstOccurrence.containsKey(state)) {
maxLength = Math.max(maxLength, i - firstOccurrence.get(state));
} else {
firstOccurrence.put(state, i);
}
}
return maxLength;
}
public static void main(String[] args) {
LongestVowelSubstring sol = new LongestVowelSubstring();
System.out.println(sol.findTheLongestSubstring("eleetminicoworoep")); // Output: 13
}
}
#include <iostream>
#include <unordered_map>
#include <vector>
int findTheLongestSubstring(const std::string& s) {
int state = 0;
int maxLength = 0;
std::unordered_map<int, int> stateMap = { {0, -1} };
for (int i = 0; i < s.size(); ++i) {
switch (s[i]) {
case 'a': state ^= (1 << 0); break;
case 'e': state ^= (1 << 1); break;
case 'i': state ^= (1 << 2); break;
case 'o': state ^= (1 << 3); break;
case 'u': state ^= (1 << 4); break;
}
if (stateMap.find(state) != stateMap.end()) {
maxLength = std::max(maxLength, i - stateMap[state]);
} else {
stateMap[state] = i;
}
}
return maxLength;
}
int main() {
std::string s = "eleetminicoworoep";
std::cout << findTheLongestSubstring(s) << std::endl; // Output: 13
return 0;
}
function findTheLongestSubstring(s) {
let mask = 0;
const stateMap = {0: -1};
let maxLength = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === 'a') mask ^= (1 << 0);
else if (s[i] === 'e') mask ^= (1 << 1);
else if (s[i] === 'i') mask ^= (1 << 2);
else if (s[i] === 'o') mask ^= (1 << 3);
else if (s[i] === 'u') mask ^= (1 << 4);
if (mask in stateMap) {
maxLength = Math.max(maxLength, i - stateMap[mask]);
} else {
stateMap[mask] = i;
}
}
return maxLength;
}
console.log(findTheLongestSubstring("eleetminicoworoep")); // Output: 13
#include <stdio.h>
#include <string.h>
int findTheLongestSubstring(char * s){
int n = strlen(s);
int state = 0, maxLength = 0;
int first_occurrence[32];
memset(first_occurrence, -1, sizeof(first_occurrence));
first_occurrence[0] = 0;
for (int i = 0; i < n; ++i) {
switch (s[i]) {
case 'a': state ^= 1 << 0; break;
case 'e': state ^= 1 << 1; break;
case 'i': state ^= 1 << 2; break;
case 'o': state ^= 1 << 3; break;
case 'u': state ^= 1 << 4; break;
default: break;
}
if (first_occurrence[state] == -1) {
first_occurrence[state] = i + 1;
} else {
int len = i + 1 - first_occurrence[state];
if (len > maxLength) maxLength = len;
}
}
return maxLength;
}
int main() {
char s[] = "eleetminicoworoep";
printf("%d\n", findTheLongestSubstring(s)); // Output: 13
return 0;
}
using System;
using System.Collections.Generic;
public class Solution {
public int FindTheLongestSubstring(string s) {
int maxLength = 0, mask = 0;
Dictionary<int, int> firstOccurrence = new Dictionary<int, int>();
firstOccurrence[0] = -1;
for (int i = 0; i < s.Length; i++) {
switch (s[i]) {
case 'a': mask ^= (1 << 0); break;
case 'e': mask ^= (1 << 1); break;
case 'i': mask ^= (1 << 2); break;
case 'o': mask ^= (1 << 3); break;
case 'u': mask ^= (1 << 4); break;
}
if (firstOccurrence.ContainsKey(mask)) {
maxLength = Math.Max(maxLength, i - firstOccurrence[mask]);
} else {
firstOccurrence[mask] = i;
}
}
return maxLength;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.FindTheLongestSubstring("eleetminicoworoep")); // Output: 13
}
}The Python approach uses a dictionary to keep a record of earlier states along with the current state check to find the maximum possible even-count substring effectively.
Time Complexity: O(n), since we iterate through the string once.
Space Complexity: O(1), given the limited, fixed-size state storage.
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).
function findTheLongestSubstring(s: string): number {
const vowels = 'aeiou';
const d: number[] = Array(32).fill(1 << 29);
d[0] = 0;
let [ans, mask] = [0, 0];
for (let i = 1; i <= s.length; i++) {
const c = s[i - 1];
for (let j = 0; j < 5; j++) {
if (c === vowels[j]) {
mask ^= 1 << j;
break;
}
}
ans = Math.max(ans, i - d[mask]);
d[mask] = Math.min(d[mask], i);
}
return ans;
}func findTheLongestSubstring(s string) (ans int) {
vowels := "aeiou"
d := [32]int{}
for i := range d {
d[i] = 1 << 29
}
d[0] = 0
mask := 0
for i := 1; i <= len(s); i++ {
c := s[i-1]
for j := 0; j < 5; j++ {
if c == vowels[j] {
mask ^= 1 << j
break
}
}
ans = max(ans, i-d[mask])
d[mask] = min(d[mask], i)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Bitmask to Track Vowel Counts | Time Complexity: O(n), where n is the length of the string, because we traverse it once. |
| Using Prefix Parity Tracking | Time Complexity: O(n), since we iterate through the string once. |
| Prefix XOR + Array or Hash Table | – |
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. |
Frequently asked questions
Is Find the Longest Substring Containing Vowels in Even Counts easy or hard?
The problem is classified as Medium difficulty on LeetCode. The challenge is recognizing that vowel counts only matter by parity and can be represented with a 5-bit mask. Once this insight is discovered, the implementation becomes straightforward and runs in linear time.
Find the Longest Substring Containing Vowels in Even Counts Python/Java solution
Python and Java implementations typically use an integer bitmask and a dictionary or array to store the first index of each state. As you iterate through the string, toggle the corresponding vowel bit and check if the state has appeared before. If it has, update the maximum substring length. The implementation runs in O(n) time with constant space.
How to solve Find the Longest Substring Containing Vowels in Even Counts in O(n)?
Maintain a 5-bit mask representing whether each vowel has appeared an odd or even number of times. Iterate through the string and toggle the bit for a vowel whenever it appears. Track the first index where each mask occurs using a hash map. If the same mask appears again, the substring between those indices has even counts for all vowels, and you update the maximum length.
What is the best approach for Find the Longest Substring Containing Vowels in Even Counts?
The best approach uses a 5-bit bitmask to track the parity of each vowel while scanning the string once. Store the earliest index where each mask appears and update the maximum substring length when the same mask reappears. This works because matching masks indicate that all vowels between the two positions occur an even number of times. The solution runs in O(n) time and O(1) space.
Is Find the Longest Substring Containing Vowels in Even Counts asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving prefix parity states and bitmask tracking. Variants of this technique appear in interviews at companies like Google, Amazon, and Meta when testing string processing, prefix techniques, and bit manipulation skills.
What data structure is used in Find the Longest Substring Containing Vowels in Even Counts?
The solution primarily uses a hash table (or array of size 32) to store the earliest index for each vowel parity mask. Bit manipulation represents vowel states efficiently, and prefix traversal processes the string in linear time.
What is the time complexity of Find the Longest Substring Containing Vowels in Even Counts?
The optimal algorithm runs in O(n) time because the string is scanned once while updating a bitmask and performing constant-time hash lookups. Space complexity is O(1) since there are only 32 possible vowel parity states (2^5). Each state stores its first occurrence index.