Introduction

In this blog post, we will explore how to solve the LeetCode problem "1371" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's a breakdown of the solution:

• Prefix XOR States: Use a bitmask to represent the parity (even/odd count) of each vowel. Each bit in the mask corresponds to a vowel (a, e, i, o, u). We compute the XOR of vowel counts for each prefix of the string.

• Hash Map Optimization: Store the first occurrence of each bitmask (XOR state) in a hash map (dictionary). If we encounter the same mask again, it means the substring between those two occurrences has an even count of each vowel.

• Maximize Length: Iterate through the string, updating the XOR mask and the hash map. The longest substring with even vowel counts is the maximum difference between the current index and the first occurrence of the current XOR mask.

• Runtime & Space Complexity: O(n), O(1) since the hash map can contain at most 2^5 = 32 entries, which is constant.

Code

    def longest_substring_with_even_vowels(s: str) -> int:
    """
    Finds the length of the longest substring containing each vowel an even number of times.
    """

    vowel_map = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
    state = 0
    first_occurrence = {0: -1}  # Store first occurrence of each state
    max_length = 0

    for i, char in enumerate(s):
        if char in vowel_map:
            state ^= (1 << vowel_map[char])

        if state in first_occurrence:
            max_length = max(max_length, i - first_occurrence[state])
        else:
            first_occurrence[state] = i

    return max_length