Find The Longest Substring Containing Vowels In Even Counts - Leetcode Solution

Problem:

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, for every vowel in the substring, the count of that vowel must be even.

Example 1:

Input: s = "eleetminicoworoep" Output: 13 Explanation: The longest substring is "leetminicowor" which contains two e's, two i's, two o's, and two u's.

Example 2:

Input: s = "leetcodeisgreat" Output: 5

Example 3:

Input: s = "bcbcbc" Output: 6

Approach:

The approach to solve this problem is to use bitmasking and sliding window technique. We can use a bitmask to keep track of the counts of each vowel in the current substring. We can set the i-th bit of the bitmask to 1 if the count of the i-th vowel in the substring is odd, and to 0 if the count is even.

We can then iterate through the string s, updating the bitmask and keeping track of the start and end indices of the current substring. If the bitmask is the same at the start and end of the substring, then the substring contains each vowel an even number of times.

We can keep track of the length of the longest such substring seen so far, and return it at the end.

Solution:

We will define a function to check if a character is a vowel or not.

For each character in string s, we will update the count of vowels in the current substring and use a bitmask to represent whether the counts of each vowel are even or odd.

If the bitmask at the start and end of the substring are the same, then the substring contains each vowel an even number of times, so we will update the length of the longest substring seen so far.

At the end, we will return the length of the longest substring seen so far.

Here is the Python code for the solution:

def findTheLongestSubstring(s: str) -> int: vowels = 'aeiou' # Dictionary to store bitmask at each index bitmask = {0: -1} # Initialize variables for current bitmask and longest substring curr_bitmask = 0 max_len = 0 # Iterate through string s for i, c in enumerate(s): # If c is a vowel, update count in current bitmask if c in vowels: # Get index of c in vowels vowel_idx = vowels.index(c) # Update current bitmask curr_bitmask ^= 1 << vowel_idx # If this bitmask has not been seen before, store it if curr_bitmask not in bitmask: bitmask[curr_bitmask] = i # If the current bitmask has been seen before, update max_len accordingly else: max_len = max(max_len, i - bitmask[curr_bitmask]) return max_len

Time Complexity:

The time complexity of the above solution is O(n), where n is the length of the input string s. This is because we iterate through the string s only once.

Space Complexity:

The space complexity of the above solution is O(1) since the maximum size of the bitmask is 32 (as there are 5 vowels) and the maximum size of the dictionary is also 32.

1