1371. Find the Longest Substring Containing Vowels in Even Counts

// 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;
    }
}