BinarySearch 0710 Longest Substring with Even Vowel Counts

Problem statement

https://binarysearch.com/problems/Longest-Substring-with-Even-Vowel-Counts/

Solution

Equal to Leetcode 1371. Find the Longest Substring Containing Vowels in Even Counts

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        d = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
        acc = [0]
        d2 = defaultdict(list)
        d2[0] = [0]
        for i, x in enumerate(s):
            acc += [acc[-1] ^ 1<<(d[x])] if x in d else [acc[-1]]
            d2[acc[-1]] += [i + 1]

        return max(x[-1] - x[0] for x in d2.values())