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.
using System;
using System.Collections.Generic;
public class Solution {
public int FindTheLongestSubstring(string s) {
int maxLength = 0, mask = 0;
Dictionary<int, int> firstOccurrence = new Dictionary<int, int>();
firstOccurrence[0] = -1;
for (int i = 0; i < s.Length; i++) {
switch (s[i]) {
case 'a': mask ^= (1 << 0); break;
case 'e': mask ^= (1 << 1); break;
case 'i': mask ^= (1 << 2); break;
case 'o': mask ^= (1 << 3); break;
case 'u': mask ^= (1 << 4); break;
}
if (firstOccurrence.ContainsKey(mask)) {
maxLength = Math.Max(maxLength, i - firstOccurrence[mask]);
} else {
firstOccurrence[mask] = i;
}
}
return maxLength;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.FindTheLongestSubstring("eleetminicoworoep")); // Output: 13
}
}
This C# code uses a combination of bit manipulation and dictionary storage for efficient lookup and computation of substrings that maintain even occurrences of vowels.