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

Problem statement

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/

Solution

Use cumulative bitmask, where we keep 1 for bit if we have odd number of letter.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def findTheLongestSubstring(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())