Leetcode Daily Question 15/09/2024 - 1371. Find the Longest Substring Containing Vowels in Even Counts

Problem Description:

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.

class Solution:
  def findTheLongestSubstring(self, s: str) -> int:
    vowels = {"a":0,"e":1,"i":2,"o":3,"u":4}
    max_length = 0
    mask = 0
    mask_map = {0: -1}
    
    for i, char in enumerate(s):
      if char in vowels:
        mask ^= (1 << vowels[char])
      if mask in mask_map:
        max_length = max(max_length, i - mask_map[mask])
      else:
        mask_map[mask] = i
    
    return max_length

Explanation:

We use bitmask to solve this problem. A bitmask is a way to code information about certain values. In this case we use a bitmask with 5 bits representing the parity of vowel count, with each vowel representing each bit.

When the bit is 0, it means that the count of that particular vowel is even in the current substring. Whereas 1 means the count of the vowel is odd.

vowels = {"a":0,"e":1,"i":2,"o":3,"u":4}
max_length = 0

We then keep track of the first occurrence of each vowel and its index using the mask_map hash map.

This way, every time we encounter that same vowel, we update the max_length. And every time we meet the same bit mask we know we have an even number of that vowel.

Consider the following example:

mask = 0 
mask_map = {0: -1}

s = "eleetminicoworoep"

i = 0 char = "e"
This is a vowel and vowels[char] = 1
So mask = mask ^ (1 << vowels[char]) = 0 ^ (1 << 1) = 0 ^ 10 = 10
This is the first occurrence of "e", so we add it to the mask map
mask_map = {0: -1, 10: 0}

i = 1 char = "l"
This is not a vowel so we update max_length = 0

i = 2 char = "e"
This is a vowel and vowels[char] = 1
So mask = 10 ^ 10 = 0
This we have alrady seen 0 in mask_map, so we update the max length instead
max_length = max(max_length, i - mask_map[mask]) = max(0, 2 - (-1)) = 3

This is equivalent to the substirng "ele" which has an even number of vowels.


Continue like this, we will find that max_length = 13 equating to the string "leetminicowor"

Here is the logic for the for loop.

for i, char in enumerate(s):
  if char in vowels:
    mask ^= (1 << vowels[char]) 
  if mask in mask_map:
    max_length = max(max_length, i - mask_map[mask])
  else:
    mask_map[mask] = i
  
  return max_length

The time complexity is O(n) as we need to iterate through the entire string exactly once.

The space complexity is O(n) as we need to store the first occurrence of each vowel.

The full solution can be found near the top of the page.