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
2using System;
3using System.Collections.Generic;
4
5public class Solution {
6 public int FindTheLongestSubstring(string s) {
7 Dictionary<int, int> state = new Dictionary<int, int>();
8 state[0] = -1;
9 int maxLength = 0, mask = 0;
10
11 for (int i = 0; i < s.Length; i++) {
12 switch (s[i]) {
13 case 'a': mask ^= (1 << 0); break;
14 case 'e': mask ^= (1 << 1); break;
15 case 'i': mask ^= (1 << 2); break;
16 case 'o': mask ^= (1 << 3); break;
17 case 'u': mask ^= (1 << 4); break;
18 }
19 if (state.ContainsKey(mask)) {
20 maxLength = Math.Max(maxLength, i - state[mask]);
21 } else {
22 state[mask] = i;
23 }
24 }
25 return maxLength;
26 }
27
28 public static void Main() {
29 Solution sol = new Solution();
30 Console.WriteLine(sol.FindTheLongestSubstring("eleetminicoworoep")); // Output: 13
31 }
32}
33This solution in C# uses a Dictionary to keep track of the first occurrence of each bitmask. The iteration adjusts the bitmask and checks against known states to determine the length of valid substrings.
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.