We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Longest Substring Containing Vowels in Even Counts

Difficulty: Medium

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.

Key Insights

  • Vowels can be represented by their parity (even or odd) using bits.
  • A bitmask can be used to track the parity of each vowel as we traverse the string.
  • Using a hash table (dictionary) to store the first occurrence of each bitmask allows us to calculate the length of substrings efficiently.
  • The longest valid substring occurs when the current bitmask matches a previously seen bitmask.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (for bitmask states) + O(n) (for hash table)

Solution

The solution utilizes a bitmask to represent the parity (even or odd) of each vowel. Each vowel corresponds to a specific bit in the bitmask. As we iterate through the string, we update the bitmask based on the current vowel encountered. We check if the current bitmask has been seen before using a hash table to keep track of the first index where each bitmask was encountered. If it has, the length of the substring from that index to the current index is calculated, and we update the maximum length accordingly.

Code Solutions

def findTheLongestSubstring(s: str) -> int:
    # Create a dictionary to store the first occurrence of each bitmask
    mask_index = {0: -1}  # Initial mask is 0 at index -1
    max_length = 0
    mask = 0  # Bitmask to track the parity of vowels

    # Map vowels to their corresponding bit positions
    vowel_to_bit = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}

    for i, char in enumerate(s):
        if char in vowel_to_bit:
            # Toggle the corresponding bit for the vowel
            mask ^= (1 << vowel_to_bit[char])

        # Check if this mask has been seen before
        if mask in mask_index:
            # Calculate the length of the substring
            length = i - mask_index[mask]
            max_length = max(max_length, length)
        else:
            # Store the first occurrence of this mask
            mask_index[mask] = i

    return max_length
← Back to All Questions