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
2function findTheLongestSubstring(s) {
3 let state = {0: -1};
4 let maxLength = 0, mask = 0;
5
6 for (let i = 0; i < s.length; i++) {
7 switch (s[i]) {
8 case 'a': mask ^= (1 << 0); break;
9 case 'e': mask ^= (1 << 1); break;
10 case 'i': mask ^= (1 << 2); break;
11 case 'o': mask ^= (1 << 3); break;
12 case 'u': mask ^= (1 << 4); break;
13 }
14 if (state.hasOwnProperty(mask)) {
15 maxLength = Math.max(maxLength, i - state[mask]);
16 } else {
17 state[mask] = i;
18 }
19 }
20 return maxLength;
21}
22
23console.log(findTheLongestSubstring("eleetminicoworoep")); // Output: 13
24This JavaScript implementation applies a similar logic using objects to keep track of the first occurrence of each state and updating the current mask index accordingly.
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.