LC-1371 Medium LeetCode

1371. Find the Longest Substring Containing Vowels in Even Counts

Hash Table String Bit Manipulation Prefix Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 76% Topics: Hash Table, String, Bit Manipulation, Prefix Sum

Reading material

Arrays & Hashing 12 min Strings 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def findTheLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        VOWELS = "aeiou"
        result, mask, lookup = 0, 0, [-2]*(2**len(VOWELS))
        lookup[0] = -1
        for i, c in enumerate(s):
            index = VOWELS.find(c)
            mask ^= (1 << index) if index >= 0 else 0
            if lookup[mask] == -2:
                lookup[mask] = i
            result = max(result, i-lookup[mask])
        return result

Solution from kamyu104/LeetCode-Solutions · MIT