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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Longest Substring Containing Vowels in Even Counts

Number: 1473

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Meta, Microsoft

Problem Description

Given a string s, return the size of the longest substring in which each of the five vowels ('a', 'e', 'i', 'o', 'u') appears an even number of times. If a vowel does not appear in the substring, it is considered to appear 0 times, which is even.

Key Insights

  • Instead of counting vowels in every possible substring (which is inefficient), maintain a prefix parity state.
  • Use a bitmask with 5 bits, where each bit corresponds to one vowel. A bit is toggled (using XOR) when that vowel is encountered.
  • When the same bitmask appears again, it indicates that the vowels between these two indices have even counts.
  • Use a dictionary (or hashmap) to record the first occurrence of each bitmask state.
  • The problem is then reduced to finding the maximum distance between two indices with the same parity state.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we traverse it once. Space Complexity: O(2^5) = O(1) for storing 32 possible states in the hashmap, plus O(n) for the input.

Solution

The solution employs a bit manipulation based approach combined with a prefix sum idea. Each vowel is assigned to one of the five bits in the bitmask (e.g., bit0 for 'a', bit1 for 'e', etc.). As you iterate over the string, the current state of vowels is updated by toggling the corresponding bit when a vowel is encountered. A hashmap is used to store the earliest index where each state is seen. If the same state is encountered again, the substring between these two indices must contain vowels that appear an even number of times, and its length is considered as a candidate for the answer.

Code Solutions

# Python solution with detailed comments

def findTheLongestSubstring(s: str) -> int:
    # Define a mapping from vowels to corresponding bits in the bitmask.
    vowel_to_bit = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
    
    # Dictionary to store the first occurrence of each state.
    state_to_index = {0: -1}  # Initial state before any characters is at index -1.
    max_length = 0  # Variable to keep track of maximum substring length.
    current_state = 0  # Bitmask state initializing with 0 (even counts for all vowels).
    
    # Iterate over each character in the string.
    for index, char in enumerate(s):
        # If the character is a vowel, toggle the corresponding bit.
        if char in vowel_to_bit:
            current_state ^= vowel_to_bit[char]
        # If current state was seen before, update the maximum substring length.
        if current_state in state_to_index:
            max_length = max(max_length, index - state_to_index[current_state])
        else:
            # Otherwise, record the first occurrence of this state.
            state_to_index[current_state] = index
    return max_length

# Example usage:
print(findTheLongestSubstring("eleetminicoworoep"))
← Back to All Questions