Sponsored
Sponsored
This approach uses a bitmask to represent the parity (even or odd) of each vowel count. We traverse the string, updating the bitmask each time we encounter a vowel. The key observation is that if two prefixes have the same bitmask state, the substring between them has an even count of vowels.
Time Complexity: O(n), as we traverse through the string once.
Space Complexity: O(1), only a constant space for the state array of size 32 (2^5).
1
2def findTheLongestSubstring(s: str) -> int:
3 state = {0: -1} # Initial condition, state 0 starts at index -1
4 maxLength = mask = 0
5 for i, char in enumerate(s):
6 if char == 'a':
7 mask ^= (1 << 0)
8 elif char == 'e':
9 mask ^= (1 << 1)
10 elif char == 'i':
11 mask ^= (1 << 2)
12 elif char == 'o':
13 mask ^= (1 << 3)
14 elif char == 'u':
15 mask ^= (1 << 4)
16 # Check if mask has been seen before
17 if mask in state:
18 maxLength = max(maxLength, i - state[mask])
19 else:
20 state[mask] = i
21 return maxLength
22
23print(findTheLongestSubstring("eleetminicoworoep")) # Output: 13
24In the Python solution, a dictionary tracks the first occurrence of each bitmask. The bitmask is updated through a simple toggle switch for each vowel, and the length of any consecutive repeated pattern of bitmasks denotes a valid substring.
In this approach, we will track the parity (even or odd) of the number of occurrences of the vowels using prefix arrays. By storing these in prefix counts we can determine substrings where all vowel counts are even.
Time Complexity: O(n), where n is the length of the string, as we iterate over it.
Space Complexity: O(1), by using a fixed-size array to store the first occurrence of each state.
In this solution, we use an array to store the first time a specific parity configuration is encountered. This allows the efficient calculation of possible substrings at each step.