Find the Longest Substring Containing Vowels in Even Counts

MEDIUM

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.

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

Checkout 2 different approaches to solve Find the Longest Substring Containing Vowels in Even Counts. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra space to store the vowel counts (an array of size 5).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Longest Substring Containing Vowels in Even Counts. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Find the Longest Substring Containing Vowels in Even Counts

Patterns:

Bit ManipulationPrefix Sum

Data Structures:

Hash TableString