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.
For example:
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.
s
= "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.
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.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force method for this problem involves examining every possible substring within the given string. For each substring, we count the number of times each vowel appears. We then check if all vowels appear an even number of times, and if so, we compare the length of that substring with the longest valid substring found so far.
Here's how the algorithm would work step-by-step:
def find_longest_substring_with_even_vowel_counts_brute_force(input_string):
longest_substring_length = 0
for substring_start_index in range(len(input_string)):
for substring_end_index in range(substring_start_index, len(input_string)):
substring = input_string[substring_start_index:substring_end_index + 1]
# Initialize vowel counts for this substring
vowel_counts = {
'a': 0,
'e': 0,
'i': 0,
'o': 0,
'u': 0
}
for char in substring:
if char in 'aeiou':
vowel_counts[char] += 1
# Check if all vowel counts are even
all_vowels_even = True
for vowel_count in vowel_counts.values():
if vowel_count % 2 != 0:
all_vowels_even = False
break
# If all vowels appear an even number of times,
# update the longest substring length if needed
if all_vowels_even:
current_substring_length = len(substring)
# Check if this is the longest valid substring we've seen
if current_substring_length > longest_substring_length:
longest_substring_length = current_substring_length
return longest_substring_length
The efficient approach focuses on tracking the parity (even or odd) of vowel counts within the substring. By cleverly using this information, we can identify potential longest substrings that satisfy the even count requirement, avoiding the need to check every possible substring.
Here's how the algorithm would work step-by-step:
def find_longest_substring_containing_vowels_in_even_counts(input_string):
vowel_indices = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
string_length = len(input_string)
max_length = 0
# Store the first occurrence of each vowel parity record.
first_occurrence = {0: -1}
vowel_parity = 0
for index in range(string_length):
character = input_string[index]
if character in vowel_indices:
vowel_index = vowel_indices[character]
vowel_parity ^= (1 << vowel_index)
# If this parity has been seen before
if vowel_parity in first_occurrence:
max_length = max(max_length, index - first_occurrence[vowel_parity])
else:
# Store the index of first occurance
first_occurrence[vowel_parity] = index
else:
#if parity not seen store the index
if vowel_parity not in first_occurrence:
first_occurrence[vowel_parity] = index
if vowel_parity in first_occurrence:
max_length = max(max_length, index - first_occurrence[vowel_parity])
return max_length
Case | How to Handle |
---|---|
Null or empty input string | Return 0 immediately, as an empty string trivially satisfies the condition of even vowel counts. |
Input string with no vowels | The entire string is a valid substring since all vowels have a count of 0 (even), so return the string's length. |
Input string with all vowels having even counts | The entire string is a valid substring, so return the string's length. |
Input string of length 1 | If the single character is a vowel, return 0; otherwise, return 1. |
Input string with only one vowel appearing an odd number of times | The longest valid substring will exclude that single vowel, requiring us to search for valid substrings within the string. |
Input string with all vowels appearing an odd number of times | The longest valid substring would need to exclude at least one occurrence of each vowel to make the counts even; our algorithm needs to efficiently explore all substrings. |
Long input string to ensure the algorithm has O(n) time complexity. | Prefix sum and bit manipulation allows us to determine if a given substring has even counts of all vowels, so the runtime should be O(n). |
Input string with a vowel appearing many times consecutively at the beginning or end. | The algorithm should handle consecutive vowels correctly, updating the bitmask based on the vowel counts so the substring with the longest valid length is correctly computed. |