Find the Longest Substring Containing Vowels in Even Counts

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^5 s contains only lowercase English letters.

def longest_substring_with_even_vowels(s: str) -> int:
    """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.
    """
    vowels = "aeiou"
    vowel_indices = {v: i for i, v in enumerate(vowels)}
    
    # Initialize the state (bitmask) to index mapping.
    # state = 0 means all vowels appear an even number of times.
    # state = 1 means 'a' appears an odd number of times.
    # state = 2 means 'e' appears an odd number of times.
    # state = 3 means 'a' and 'e' appear an odd number of times, and so on.
    state_to_index = {0: -1}
    state = 0
    max_len = 0
    
    for i, char in enumerate(s):
        if char in vowels:
            vowel_index = vowel_indices[char]
            state ^= (1 << vowel_index)
        
        if state in state_to_index:
            max_len = max(max_len, i - state_to_index[state])
        else:
            state_to_index[state] = i
            
    return max_len

# Example Usage
print(longest_substring_with_even_vowels("eleetminicoworoep"))  # Output: 13
print(longest_substring_with_even_vowels("leetcodeisgreat")) # Output: 5
print(longest_substring_with_even_vowels("bcbcbc")) # Output: 6

Explanation:

1. Problem Understanding: The goal is to find the longest substring where each vowel ('a', 'e', 'i', 'o', 'u') appears an even number of times. This includes zero occurrences, which are considered even.

2. Naive Approach (Brute Force): A naive approach would be to check every possible substring and count the occurrences of each vowel. This would involve nested loops to generate substrings and then a loop to count vowels, leading to a high time complexity, specifically O(n^3) where n is the length of the string.

   def longest_substring_naive(s: str) -> int:
       max_len = 0
       for i in range(len(s)):  # O(n)
           for j in range(i, len(s)):  # O(n)
               sub = s[i:j+1]
               counts = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
               for char in sub:  # O(n)
                   if char in counts:
                       counts[char] += 1
               even = True
               for count in counts.values():
                   if count % 2 != 0:
                       even = False
                       break
               if even:
                   max_len = max(max_len, len(sub))
       return max_len
   

3. Optimal Approach (Using Bit Manipulation and Prefix States): We can optimize this by using bit manipulation to represent the state of vowels (whether they appear an even or odd number of times) and a dictionary to store the first occurrence of each state.

   • Bitmasking Vowel Counts: Assign each vowel a bit (a=0, e=1, i=2, o=3, u=4). Maintain a state using an integer where each bit represents whether the vowel count is odd (1) or even (0). If 'a' appears an odd number of times, the 0th bit is set to 1. The state is XORed with the bitmask each time a vowel is encountered.
   • State Tracking: Use a dictionary state_to_index to keep track of the first occurrence of each state. The key is the state (bitmask), and the value is the index of the first time that state was seen. If the same state is encountered again at a later index, it means the vowels between these two indices have appeared an even number of times.

4. Step-by-step breakdown

• `vowels =