Find the Longest Substring Containing Vowels in Even Counts Solution
Find the Longest Substring Containing Vowels in Even Counts solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Longest Substring Containing Vowels in Even Counts is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Bit Manipulation, Prefix Sum
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the length of the longest substring of s in which each of the five vowels a, e, i, o and u appears an even number of times. Zero counts as even.
Example 1
Input: s = "eleetminicoworoep"
Output: 13
Explanation: "leetminicowor" has two e's, two o's and two i's.
Example 2
Input: s = "leetcodeisgreat"
Output: 5
Explanation: "leetc" has two e's and no other vowel.
Example 3
Input: s = "bcbcbc"
Output: 6
Explanation: No vowels at all, so the whole string qualifies.
Constraints
1 <= s.length <= 100000s consists of lowercase English letters.
Hints for Find the Longest Substring Containing Vowels in Even Counts
Hint 1
Only the parity of each vowel count matters, which is five bits of state.
Hint 2
A substring has all-even vowel counts exactly when the parity state at its two ends is the same.
Hint 3
So record the first index at which each of the 32 states appears and measure the widest repeat.
How to solve Find the Longest Substring Containing Vowels in Even Counts
Track a 5-bit parity mask over the vowels. Two positions with the same mask bracket a substring where every vowel appeared an even number of times, so the answer is the widest gap between equal masks.
Approach
- Start with state
0recorded at index-1, standing for the empty prefix. - Sweep the string, toggling the bit for each vowel encountered.
- If the current state has not been seen, record its index; otherwise the candidate length is
i - first[state]. - Return the largest candidate.
Why it works
The parity mask is the XOR of the vowel indicators seen so far. Equal masks at positions i < j mean every vowel toggled an even number of times in between. Keeping only the first occurrence of each state maximises the distance, and seeding state 0 at -1 lets the answer start at index 0.
Complexity
- Time —
O(n) - Space —
O(32)
Pitfalls
- Overwriting the stored index gives the shortest such substring, not the longest.
- Forgetting the
-1seed misses substrings that begin at the start of the string. - Non-vowel characters leave the state untouched, which is what makes an all-consonant string fully qualify.
Reference solution
Python
def findTheLongestSubstring(s: str) -> int:
first = {0: -1}
state = 0
best = 0
for i, c in enumerate(s):
idx = "aeiou".find(c)
if idx >= 0:
state ^= 1 << idx
if state in first:
best = max(best, i - first[state])
else:
first[state] = i
return bestJava
public static int findTheLongestSubstring(String s) {
int[] first = new int[32];
Arrays.fill(first, -2);
first[0] = -1;
int state = 0, best = 0;
String vowels = "aeiou";
for (int i = 0; i < s.length(); i++) {
int idx = vowels.indexOf(s.charAt(i));
if (idx >= 0) state ^= 1 << idx;
if (first[state] == -2) first[state] = i;
else best = Math.max(best, i - first[state]);
}
return best;
}C++
int findTheLongestSubstring(string s) {
vector<int> first(32, -2);
first[0] = -1;
int state = 0, best = 0;
string vowels = "aeiou";
for (int i = 0; i < (int) s.size(); i++) {
size_t idx = vowels.find(s[i]);
if (idx != string::npos) state ^= 1 << (int) idx;
if (first[state] == -2) first[state] = i;
else best = max(best, i - first[state]);
}
return best;
}JavaScript
var findTheLongestSubstring = function(s) {
var first = {};
first["0"] = -1;
var state = 0, best = 0;
for (var i = 0; i < s.length; i++) {
var idx = "aeiou".indexOf(s.charAt(i));
if (idx >= 0) state ^= 1 << idx;
var key = String(state);
if (first[key] === undefined) first[key] = i;
else if (i - first[key] > best) best = i - first[key];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets