Find the Longest Substring Containing Vowels in Even Counts
MedPrompt
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^5scontains only lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
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
ifrom0tos.length() - 1. - For each
i, start a nested loop with an ending indexjfromitos.length() - 1. - Maintain an array
vowelCountsof size 5 to store the counts of 'a', 'e', 'i', 'o', 'u' for the substrings.substring(i, j+1). - In the inner loop, as
jincreases, update thevowelCountsfor the characters.charAt(j). - After updating the counts, check if all counts in
vowelCountsare even. - If all vowel counts are even, update
maxLength = max(maxLength, j - i + 1). - After the loops complete, return
maxLength.
Walkthrough
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
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).
Trade-offs
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.
Solutions
Solution
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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.