1371. Find the Longest Substring Containing Vowels in Even Counts

Hash Table String Bit Manipulation Prefix Sum

Time: O(n)

Space: O(32)

Intuition

Use bitmask for vowel parity. XOR mask at each position. Longest subarray with same mask = first occurrence of each mask. Use prefix XOR approach.

Algorithm

15 vowels → 5-bit mask. State[i] = XOR mask of vowels seen so far.
2If state[i] == state[j]: subarray (i+1)..j has even count of all vowels.
3Store first occurrence of each state. Answer = max(i - first[state[i]]).

Common Pitfalls

•Initialize first[0] = -1 (empty prefix has all even counts). 5 vowels → 32 possible states.

1371.cs

// Approach: XOR bitmask tracks parity of each vowel; store first occurrence of each bitmask state; answer is max(i - first[prefix]).
// Time: O(n) Space: O(32)

public class Solution
{
    public int FindTheLongestSubstring(string s)
    {
        const string kVowels = "aeiou";
        int ans = 0;
        int prefix = 0; // the binary prefix
        Dictionary<int, int> prefixToIndex = new Dictionary<int, int>();
        prefixToIndex[0] = -1;

        for (int i = 0; i < s.Length; ++i)
        {
            int index = kVowels.IndexOf(s[i]);
            if (index != -1)
                prefix ^= 1 << index;
            if (!prefixToIndex.ContainsKey(prefix))
                prefixToIndex[prefix] = i;
            ans = Math.Max(ans, i - prefixToIndex[prefix]);
        }

        return ans;
    }
}

Was this solution helpful?