# Find the Longest Substring Containing Vowels in Even Counts
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts)
Canonical: https://scaleengineer.com/dsa/problems/find-the-longest-substring-containing-vowels-in-even-counts
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force with Optimized Counting
This approach involves checking every possible substring of the given string `s`. For each substring, we count the occurrences of each vowel and check if all counts are even. To optimize the counting process, we can maintain a running count of vowels as we extend the substring, rather than recounting from scratch for every substring.
**Time:** O(N^2), where N is the length of the string. We have two nested loops to iterate through all possible substrings. The work inside the inner loop is O(1). · **Space:** O(1), as we only use a constant amount of extra space to store the vowel counts (an array of size 5).
**Pros:** Conceptually simple and easy to implement.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for large input strings as specified in the constraints.
### Explanation
The brute-force method systematically checks every single substring. It uses two nested loops to define the start and end points of a substring. For each substring, it maintains a count of each vowel. If all vowel counts are even, it compares the current substring's length with the maximum length found so far and updates it if necessary. While simple, this approach is computationally expensive.

```java
class Solution {
    public int findTheLongestSubstring(String s) {
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            // Counts for 'a', 'e', 'i', 'o', 'u'
            int[] counts = new int[5];
            for (int j = i; j < s.length(); j++) {
                char c = s.charAt(j);
                if (c == 'a') counts[0]++;
                else if (c == 'e') counts[1]++;
                else if (c == 'i') counts[2]++;
                else if (c == 'o') counts[3]++;
                else if (c == 'u') counts[4]++;
                
                if (counts[0] % 2 == 0 && counts[1] % 2 == 0 && 
                    counts[2] % 2 == 0 && counts[3] % 2 == 0 && 
                    counts[4] % 2 == 0) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Iterate through the string with a starting index `i` from `0` to `s.length() - 1`.
- For each `i`, start a nested loop with an ending index `j` from `i` to `s.length() - 1`.
- Maintain an array `vowelCounts` of size 5 to store the counts of 'a', 'e', 'i', 'o', 'u' for the substring `s.substring(i, j+1)`.
- In the inner loop, as `j` increases, update the `vowelCounts` for the character `s.charAt(j)`.
- After updating the counts, check if all counts in `vowelCounts` are even.
- If all vowel counts are even, update `maxLength = max(maxLength, j - i + 1)`.
- After the loops complete, return `maxLength`.

## Prefix State Tracking with Bitmask
This is an optimal approach that solves the problem in linear time. The core idea is to use a bitmask to represent the parity (even or odd) of the counts of each of the five vowels. A substring `s[i..j]` has an even count for each vowel if and only if the parity of vowel counts in the prefix `s[0..j]` is the same as the parity of vowel counts in the prefix `s[0..i-1]`. We can iterate through the string, calculate the parity mask for each prefix, and use a hash map (or an array) to store the first index where each mask appeared. This allows us to find the longest distance between two occurrences of the same mask.
**Time:** O(N), where N is the length of the string. We iterate through the string only once. · **Space:** O(1). We use an array of size 32 to store the first occurrence of each mask. Since the number of vowels is constant (5), the size of this array is also constant.
**Pros:** Extremely efficient with a linear time complexity.; Optimal solution for the given constraints.
**Cons:** The logic involving bitmasking and prefix states can be less intuitive to grasp compared to a brute-force solution.
### Explanation
The state of vowel counts (even or odd) can be encoded into a 5-bit integer, or a 'mask'. Each bit corresponds to a vowel. A bit is 1 if the vowel has appeared an odd number of times in the prefix, and 0 if it has appeared an even number of times. 

A substring from index `j+1` to `i` has all even vowel counts if the parity mask for the prefix `s[0...i]` is identical to the parity mask for the prefix `s[0...j]`. 

We can iterate through the string, maintaining the current prefix's mask. We use an array (or a hash map) to store the first index at which each mask value was encountered. When we encounter a mask that we've seen before, we calculate the length of the valid substring and update our maximum length. If we see a mask for the first time, we record its index.

```java
import java.util.Arrays;

class Solution {
    public int findTheLongestSubstring(String s) {
        // An array is faster than a HashMap here since keys are small integers (0-31)
        int[] firstOccurrence = new int[32];
        Arrays.fill(firstOccurrence, -2); // Use -2 to indicate not seen
        
        // A mask of 0 (all even counts) is first seen at index -1 (before the string starts)
        firstOccurrence[0] = -1;
        
        int maxLength = 0;
        int mask = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int vowelBit = -1;
            if (c == 'a') vowelBit = 0;
            else if (c == 'e') vowelBit = 1;
            else if (c == 'i') vowelBit = 2;
            else if (c == 'o') vowelBit = 3;
            else if (c == 'u') vowelBit = 4;
            
            if (vowelBit != -1) {
                // Flip the bit corresponding to the vowel
                mask ^= (1 << vowelBit);
            }
            
            // If we have seen this mask before
            if (firstOccurrence[mask] != -2) {
                // The substring between the current index and the first occurrence
                // of this mask has even counts for all vowels.
                maxLength = Math.max(maxLength, i - firstOccurrence[mask]);
            } else {
                // This is the first time we see this mask, record the index.
                firstOccurrence[mask] = i;
            }
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Create a bitmask representation for the vowels: 'a' -> bit 0, 'e' -> bit 1, 'i' -> bit 2, 'o' -> bit 3, 'u' -> bit 4.
- Initialize a variable `mask = 0`. This will track the parity of vowel counts for the current prefix of the string.
- Initialize `maxLength = 0`.
- Use an array `firstOccurrence` of size 32 (since there are 2^5 = 32 possible masks), initialized with a value indicating that no mask has been seen yet (e.g., -2). Set `firstOccurrence[0] = -1` to handle substrings starting from index 0.
- Iterate through the string `s` from index `i = 0` to `s.length() - 1`.
- For each character `s.charAt(i)`, if it's a vowel, update the `mask` by flipping the corresponding bit: `mask ^= (1 << vowel_bit)`.
- After updating the mask, check the `firstOccurrence` array:
- If `firstOccurrence[mask]` has been seen before (is not -2), it means we found a previous prefix ending at index `j = firstOccurrence[mask]` with the same vowel parity. The substring `s[j+1..i]` has the desired property. Calculate its length `i - j` and update `maxLength = max(maxLength, i - j)`.
- If `firstOccurrence[mask]` has not been seen before, store the current index: `firstOccurrence[mask] = i`.
- After the loop, return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int findTheLongestSubstring(String s) {
    int[] pos = new int[32];
    Arrays.fill(pos, Integer.MAX_VALUE);
    pos[0] = -1;
    String vowels = "aeiou";
    int state = 0;
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      for (int j = 0; j < 5; ++j) {
        if (c == vowels.charAt(j)) {
          state ^= (1 << j);
        }
      }
      ans = Math.max(ans, i - pos[state]);
      pos[state] = Math.min(pos[state], i);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findTheLongestSubstring(string s) {
    vector<int> pos(32, INT_MAX);
    pos[0] = -1;
    string vowels = "aeiou";
    int state = 0, ans = 0;
    for (int i = 0; i < s.size(); ++i) {
      for (int j = 0; j < 5; ++j)
        if (s[i] == vowels[j])
          state ^= (1 << j);
      ans = max(ans, i - pos[state]);
      pos[state] = min(pos[state], i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findTheLongestSubstring(self, s: str) -> int: pos = [inf] * 32 pos[0] = - 1 vowels = 'aeiou' state = ans = 0 for i, c in enumerate(s): for j, v in enumerate(vowels): if c == v: state ^= 1 << j ans = max(ans, i - pos[state]) pos[state] = min(pos[state], i) return ans

```