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
2#include <stdio.h>
3#include <string.h>
4
5int findTheLongestSubstring(char * s){
6 int n = strlen(s);
7 int vowelsMask = 0, maxLength = 0;
8 int state[32];
9 for (int i = 0; i < 32; i++) {
10 state[i] = -1; // Initialize all states to -1
11 }
12 state[0] = 0; // Bitmask state 0 starts at index 0
13 for (int i = 0; i < n; i++) {
14 if (s[i] == 'a') vowelsMask ^= (1 << 0);
15 else if (s[i] == 'e') vowelsMask ^= (1 << 1);
16 else if (s[i] == 'i') vowelsMask ^= (1 << 2);
17 else if (s[i] == 'o') vowelsMask ^= (1 << 3);
18 else if (s[i] == 'u') vowelsMask ^= (1 << 4);
19 if (state[vowelsMask] >= 0) {
20 maxLength = fmax(maxLength, i + 1 - state[vowelsMask]);
21 } else {
22 state[vowelsMask] = i + 1;
23 }
24 }
25 return maxLength;
26}
27
28int main() {
29 char s[] = "eleetminicoworoep";
30 printf("%d\n", findTheLongestSubstring(s)); // Output: 13
31 return 0;
32}
33The solution uses a bitmask to track vowel occurrences. The mask changes its state whenever a vowel is encountered. The state array tracks the first occurrence of each bitmask which is crucial for recognizing repeating patterns producing even counts thus finding the longest 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.
By using a state variable and a hash map tracking first occurrences, this Java solution finds the longest segment in a string where vowels appear an even number of times using efficient prefix parity.