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^5s contains only lowercase English letters.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.
C++
Java
Python
C#
JavaScript
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).
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Find the Longest Substring Containing Vowels in Even Counts with our built-in code editor and test cases.
Practice on FleetCode