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.

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.

Description Hints 2 Solution Video 24:01

1371. Find the Longest Substring Containing Vowels in Even Counts

Q: 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.

Q: 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.

Medium75.7% acceptance6 companies

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^5
s contains only lowercase English letters.

Asked at 6 companies

Microsoft Bloomberg Goldman Sachs

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

Represent the counts (odd or even) of vowels with a bitmask.

Hint 2

Precompute the prefix xor for the bitmask of vowels and then get the longest valid substring.

24:01

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findTheLongestSubstring(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"eleetminicoworoep"

Input

"leetcodeisgreat"

Input

"bcbcbc"

Your code is saved on this device.Solution