Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.
 
Example 1:
Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:
Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:
Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

 
Constraints:

1 <= s.length <= 5 x 10^5
s contains only lowercase English letters.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Data structures

Range queries

Starter code: class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        

Solutions:
class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		s = s + 'a'
		(bits, dp) = ({'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}, {0: -1})
		res = 0
		key = 0
		for (i, char) in enumerate(s):
			if char in bits:
				if key in dp:
					res = max(res, i - dp[key] - 1)
				key = key ^ 1 << bits[char]
				if key not in dp:
					dp[key] = i
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		for i in range(len(s), 0, -1):
			for j in range(len(s) - i + 1):
				sub = s[j:j + i]
				has_odd_vowel = False
				for vowel in ['a', 'e', 'i', 'o', 'u']:
					if sub.count(vowel) % 2 != 0:
						has_odd_vowel = True
						break
				if not has_odd_vowel:
					return i
		return 0


class Solution:

	def findTheLongestSubstring(self, s):
		seen = {0: -1}
		res = cur = 0
		for (i, c) in enumerate(s):
			cur ^= 1 << 'aeiou'.find(c) + 1 >> 1
			seen.setdefault(cur, i)
			res = max(res, i - seen[cur])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		seen = {0: -1}
		ans = cur = 0
		for (i, c) in enumerate(s):
			cur ^= 1 << 'aeiou'.find(c) + 1 >> 1
			seen.setdefault(cur, i)
			ans = max(ans, i - seen[cur])
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = {x: 1 << i for (i, x) in enumerate('aeiou')}
		fst = {0: -1}
		ans = mask = 0
		for (i, c) in enumerate(s):
			if c in vowels:
				mask ^= vowels[c]
			fst.setdefault(mask, i)
			ans = max(ans, i - fst[mask])
		return ans


import collections

class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		for substr_len in range(len(s), -1, -1):
			end_remove = len(s) - substr_len + 1
			for start in range(end_remove):
				even = True
				sub_str = s[start:start + substr_len]
				for vowel in 'aeiou':
					if sub_str.count(vowel) % 2 != 0:
						even = False
						break
				if even == True:
					return substr_len


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		P = [0]
		vowels = 'aeiou'
		for c in s:
			i = vowels.find(c)
			mask = 1 << i if i != -1 else 0
			P.append(P[-1] ^ mask)
		ans = 0
		fst = {}
		for (i, p) in enumerate(P):
			if p in fst:
				h = fst[p]
				ans = max(ans, i - h)
			fst.setdefault(p, i)
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:

		def countVowels(ct):
			if not ct['a'] % 2 and (not ct['e'] % 2) and (not ct['i'] % 2) and (not ct['o'] % 2) and (not ct['u'] % 2):
				return True
			return False
		for i in range(len(s)):
			ctr = collections.Counter(s[:len(s) - i])
			for j in range(i + 1):
				if j != 0:
					ctr[s[j - 1]] -= 1
					ctr[s[len(s) + j - i - 1]] += 1
				if countVowels(ctr):
					return sum(ctr.values())
		return 0


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		seen = {0: -1}
		ret = curr = 0
		for (i, c) in enumerate(s):
			curr ^= 1 << 'aeiou'.find(c) + 1 >> 1
			if curr not in seen:
				seen[curr] = i
			ret = max(ret, i - seen[curr])
		return ret


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		bits = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		seen = {0: -1}
		max_val = 0
		cur = 0
		for (i, char) in enumerate(s):
			if char in bits:
				cur ^= bits[char]
			seen.setdefault(cur, i)
			max_val = max(max_val, i - seen[cur])
		return max_val


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		m = dict(a=1, e=2, i=4, o=8, u=16)
		longest = 0
		parity_index = {0: -1}
		parity = 0
		for (i, ch) in enumerate(s):
			parity = parity ^ m.get(ch, 0)
			if parity not in parity_index:
				parity_index[parity] = i
			longest = max(longest, i - parity_index.get(parity))
		return longest


class Solution:

	def findTheLongestSubstring1(self, s: str) -> int:

		def check(L, R, cnt_memo):
			if L > R:
				return 0
			elif (L, R) in memo:
				return memo[L, R]
			elif all((v % 2 == 0 for v in list(cnt_memo.values()))):
				return R - L + 1
			else:
				old_L = L
				new_memo = {k: v for (k, v) in list(cnt_memo.items())}
				while s[L] not in 'aeiou':
					L += 1
				new_memo[s[L]] -= 1
				if new_memo[s[L]] == 0:
					del new_memo[s[L]]
				res1 = check(L + 1, R, new_memo)
				L = old_L
				old_R = R
				new_memo = {k: v for (k, v) in list(cnt_memo.items())}
				while s[R] not in 'aeiou':
					R -= 1
				new_memo[s[R]] -= 1
				if new_memo[s[R]] == 0:
					del new_memo[s[R]]
				res2 = check(L, R - 1, new_memo)
				R = old_R
				res = max(res1, res2)
				memo[L, R] = res
				return res
		cnt_memo = collections.Counter(s)
		cnt_memo = {k: v for (k, v) in list(cnt_memo.items()) if k in 'aeiou'}
		memo = dict()
		res = check(0, len(s) - 1, cnt_memo)
		return res

	def findTheLongestSubstring(self, s: str) -> int:
		res = 0
		curr = 0
		memo = dict()
		memo[0] = -1
		for (i, c) in enumerate(s):
			if c == 'a':
				curr ^= 1
			elif c == 'e':
				curr ^= 2
			elif c == 'i':
				curr ^= 4
			elif c == 'o':
				curr ^= 8
			elif c == 'u':
				curr ^= 16
			if curr in memo:
				res = max(res, i - memo[curr])
			else:
				memo[curr] = i
		return res
		return


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowel_dict = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
		integrals = [(False, False, False, False, False)]
		for l in s:
			vector = list(integrals[-1])
			if l in vowel_dict:
				vector[vowel_dict[l]] = not vector[vowel_dict[l]]
			integrals.append(tuple(vector))
		seen = {}
		res = 0
		for (i, v) in enumerate(integrals):
			if v in seen:
				res = max(res, i - seen[v])
			else:
				seen[v] = i
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		max_substring_size = 0
		processed_cons = None
		s_len = len(s)
		for i in range(s_len):
			if processed_cons == True:
				if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
					processed_cons = False
				continue
			if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
				processed_cons = False
			else:
				processed_cons = True
			if max_substring_size > s_len - i:
				break
			vowel_counts = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
			allEven = True
			for (k, letter) in enumerate(s[i:]):
				if letter in vowel_counts:
					vowel_counts[letter] += 1
					currently_all_even = True
					for count in list(vowel_counts.values()):
						if count % 2 == 1:
							currently_all_even = False
							break
					allEven = currently_all_even
				if allEven and k + 1 > max_substring_size:
					max_substring_size = k + 1
		return max_substring_size


from copy import copy

class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowel2idx = dict([(item[1], item[0]) for item in enumerate(['a', 'e', 'i', 'o', 'u'])])
		counters = [0]
		for item in s:
			counters.append(counters[-1])
			if item in vowel2idx:
				counters[-1] ^= 2 ** vowel2idx[item]
		for width in range(len(s), 0, -1):
			for start in range(len(s) - width + 1):
				if counters[start + width] ^ counters[start] != 0:
					continue
				return width
		return 0


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		(vowels, bits, dp) = ({'a', 'e', 'i', 'o', 'u'}, {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}, {0: -1})
		(res, odds) = (0, set())
		for i in range(len(s)):
			if s[i] in vowels:
				if s[i] in odds:
					odds.discard(s[i])
				else:
					odds.add(s[i])
			key = 0
			for o in odds:
				key |= 1 << bits[o]
			if key in dp:
				res = max(res, i - dp[key])
			else:
				dp[key] = i
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		states = [(False, False, False, False, False)]
		seen = {}
		mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
		for i in range(len(s)):
			vector = list(states[-1])
			character = s[i]
			if character in mapping:
				vector[mapping[character]] = not vector[mapping[character]]
			states.append(tuple(vector))
		res = 0
		for (i, v) in enumerate(states):
			if v in seen:
				res = max(res, i - seen[v])
			else:
				seen[v] = i
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		mask = 0
		mp = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
		seen = [len(s)] * 63
		seen[0] = -1
		max_len = 0
		for i in range(len(s)):
			if s[i] in 'aeiou':
				mask ^= 1 << mp[s[i]]
			seen[mask] = min(seen[mask], i)
			max_len = max(max_len, i - seen[mask])
		return max_len


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		left_states = {'': -1}
		cur_state = set()
		ans = 0
		for (i, char) in enumerate(s):
			if char in 'aeiou':
				if char in cur_state:
					cur_state.remove(char)
				else:
					cur_state.add(char)
			cur_state_str = ''.join(sorted(list(cur_state)))
			if cur_state_str in left_states:
				ans = max(ans, i - left_states[cur_state_str])
			else:
				left_states[cur_state_str] = i
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		mask = '00000'
		table = dict()
		table[mask] = -1
		vowels = 'aeiou'
		res = 0
		for (i, c) in enumerate(s):
			for j in range(5):
				if c == vowels[j]:
					mask1 = list(mask)
					mask1[j] = str(1 - int(mask1[j]))
					mask = ''.join(mask1)
			pre_idx = table.get(mask, -2)
			if pre_idx != -2:
				res = max(res, i - pre_idx)
			else:
				table[mask] = i
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		cur = 0
		res = 0
		seen = {}
		seen[0] = -1
		for (i, c) in enumerate(s):
			cur ^= 1 << 'aeiou'.find(c) + 1 >> 1
			if cur not in seen:
				seen[cur] = i
			res = max(res, i - seen[cur])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		bits = {'a': 1, 'e': 2, 'i': 3, 'o': 4, 'u': 5}
		dp = {0: -1}
		(ans, state) = (0, 0)
		for (i, c) in enumerate(s):
			if c in bits:
				state ^= 1 << bits[c]
			ans = max(ans, i - dp.get(state, 128))
			dp[state] = min(dp.get(state, 128), i)
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		current = [0, 0, 0, 0, 0]

		def convertToInteger():
			nonlocal current
			binarySum = 0
			for num in current:
				binarySum *= 2
				binarySum += num
			return binarySum

		def incrementVowels(char):
			nonlocal current
			if char == 'a':
				current[0] = 1 - current[0]
			elif char == 'e':
				current[1] = 1 - current[1]
			elif char == 'i':
				current[2] = 1 - current[2]
			elif char == 'o':
				current[3] = 1 - current[3]
			elif char == 'u':
				current[4] = 1 - current[4]
		earliest = {}
		earliest[0] = -1
		maxLength = 0
		current = [0, 0, 0, 0, 0]
		for (index, char) in enumerate(s):
			incrementVowels(char)
			binarySum = convertToInteger()
			if binarySum not in earliest:
				earliest[binarySum] = index
			else:
				maxLength = max(index - earliest[binarySum], maxLength)
		return maxLength


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = {'a': 1, 'e': 2, 'i': 3, 'o': 4, 'u': 5}
		seen = {0: -1}
		res = cur = 0
		for (i, c) in enumerate(s):
			if c in vowels:
				cur ^= 1 << vowels[c]
				seen.setdefault(cur, i)
			res = max(res, i - seen[cur])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		remainder_pos_dict = dict()
		vowels = {'a', 'e', 'i', 'o', 'u'}
		vowel_count = {ch: 0 for ch in vowels}
		max_length = 0
		for (pos, ch) in enumerate(s):
			if ch in vowels:
				vowel_count[ch] += 1
			remainders = (vowel_count['a'] % 2, vowel_count['e'] % 2, vowel_count['i'] % 2, vowel_count['o'] % 2, vowel_count['u'] % 2)
			if all(map(lambda x: x == 0, remainders)):
				max_length = max(max_length, pos + 1)
				continue
			if remainders not in remainder_pos_dict:
				remainder_pos_dict[remainders] = pos
				continue
			prefix_tail = remainder_pos_dict[remainders]
			length = pos - prefix_tail
			max_length = max(length, max_length)
		return max_length


class Solution:

	def flip(self, num, pos):
		if num & 2 ** pos:
			return num - 2 ** pos
		else:
			return num + 2 ** pos

	def findTheLongestSubstring(self, s: str) -> int:
		hash = {(0, 0, 0, 0, 0): [-1]}
		maxLen = 0
		count = {'a': 0, 'e': 0, 'i': 0, 'u': 0, 'o': 0}
		for i in range(len(s)):
			if s[i] in count:
				count[s[i]] = (count[s[i]] + 1) % 2
			set = tuple(count.values())
			if set in hash:
				hash[set].extend([i])
			else:
				hash[set] = [i]
			if len(hash[set]) >= 2:
				maxLen = max(maxLen, hash[set][-1] - hash[set][0])
		return maxLen


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		first_position = {(0, 0, 0, 0, 0): -1}
		counter = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
		ans = 0
		for (i, c) in enumerate(s):
			if c in counter:
				counter[c] += 1
			key = tuple([counter[c] % 2 for c in 'aeiou'])
			if key not in first_position:
				first_position[key] = i
			ans = max(i - first_position[key], ans)
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		seen = {(0, 0, 0, 0, 0): -1}
		counts = {c: 0 for c in 'aeiou'}
		res = 0
		for (i, ch) in enumerate(s):
			if ch in counts:
				counts[ch] += 1
			key = tuple([counts[c] % 2 for c in 'aeiou'])
			seen.setdefault(key, i)
			res = max(res, i - seen[key])
		return res


from collections import Counter

class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		_max = 0
		vowels = 'aeiou'

		def counter_to_tuple(counter):
			res = []
			for v in vowels:
				res.append(counter[v] % 2)
			return tuple(res)
		ss_counter = Counter()
		cache = {(0, 0, 0, 0, 0): -1}
		length = 0
		for (ind, ss) in enumerate(s):
			if ss in vowels:
				ss_counter[ss] += 1
			counter_tuple = counter_to_tuple(ss_counter)
			if counter_tuple in cache:
				length = max(length, ind - cache[counter_tuple])
			else:
				cache[counter_tuple] = ind
		return length


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		for window_size in range(len(s), -1, -1):
			check_range = len(s) - window_size + 1
			for i in range(check_range):
				check_wr = s[i:i + window_size]
				right_string = True
				for ch in 'aeiou':
					if check_wr.count(ch) % 2:
						right_string = False
						break
				if right_string:
					return window_size
		return 0


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		seen = {(0, 0, 0, 0, 0): -1}
		vowel = 'aeiou'
		count = [0] * 5
		ans = 0
		for i in range(len(s)):
			idx = vowel.find(s[i])
			if idx >= 0:
				count[idx] += 1
			state = tuple([count[i] % 2 for i in range(5)])
			if state in seen:
				ans = max(ans, i - seen[state])
			else:
				seen[state] = i
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		first_position = {0: -1}
		bit_ind = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
		ans = key = 0
		for (i, c) in enumerate(s):
			if c in bit_ind:
				key = key ^ 1 << bit_ind[c]
			if key not in first_position:
				first_position[key] = i
			ans = max(i - first_position[key], ans)
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		dic = {0: -1}
		n = 0
		res = 0
		voewls = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		for (i, c) in enumerate(s):
			if c in voewls:
				n ^= voewls[c]
			if n not in dic:
				dic[n] = i
			else:
				res = max(res, i - dic[n])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		cache = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		(d, k, res) = ({0: -1}, 0, 0)
		for (i, c) in enumerate(s):
			if c in cache:
				k ^= cache[c]
			if k not in d:
				d[k] = i
			else:
				res = max(res, i - d[k])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		memo = {0: 0}
		dic = dict(list(zip('aeiou', list(range(5)))))
		(curr, ans) = (0, 0)
		for (k, v) in enumerate(s, 1):
			if v in dic:
				curr ^= 1 << dic[v]
			if curr in memo:
				ans = max(ans, k - memo[curr])
			else:
				memo[curr] = k
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels_bit_mask = {v: 2 ** i for (i, v) in enumerate('aeiou')}
		vowel_state = 0
		first_index_of_recorded_state = {0: -1}
		max_substr_len = 0
		for (index, char) in enumerate(s):
			if char in vowels_bit_mask:
				vowel_state ^= vowels_bit_mask[char]
			if vowel_state in first_index_of_recorded_state:
				max_substr_len = max(max_substr_len, index - first_index_of_recorded_state[vowel_state])
			else:
				first_index_of_recorded_state[vowel_state] = index
		return max_substr_len


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		(d, n, r) = ({0: -1}, 0, 0)
		for (i, c) in enumerate(s):
			if c in vowels:
				n ^= vowels[c]
			if n not in d:
				d[n] = i
			else:
				r = max(r, i - d[n])
		return r


class Solution:

	def findTheLongestSubstring(self, S: str) -> int:
		vowels = 'aeiou'
		seen = {0: -1}
		ans = cur = 0
		for (i, c) in enumerate(S):
			if c in vowels:
				cur ^= 1 << ord(c) - 97
			if cur not in seen:
				seen[cur] = i
			else:
				ans = max(ans, i - seen[cur])
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		dict_vol = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
		dict_vol = {x: 1 << y for (x, y) in dict_vol.items()}
		previous_seen = {0: -1}
		cur = 0
		ans = 0
		for (i, c) in enumerate(s):
			if c in dict_vol:
				cur = cur ^ dict_vol[c]
			if cur not in previous_seen:
				previous_seen[cur] = i
			else:
				ans = max(ans, i - previous_seen[cur])
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		(seen, vowel) = ({0: -1}, {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4})
		res = curr = 0
		for (i, c) in enumerate(s):
			if c in vowel:
				curr ^= 1 << vowel[c]
			seen.setdefault(curr, i)
			res = max(res, i - seen[curr])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		bin_map = collections.defaultdict(int)
		for (i, c) in enumerate(['a', 'e', 'i', 'o', 'u']):
			bin_map[c] = 1 << i
		cur_bin = 0
		prev_bin = {0: -1}
		ans = 0
		for (index, c) in enumerate(s):
			cur_bin ^= bin_map[c]
			if cur_bin in prev_bin:
				ans = max(ans, index - prev_bin[cur_bin])
			else:
				prev_bin[cur_bin] = index
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		(bitmask_to_index, bitmaskrepr, result) = ({0: -1}, 0, 0)
		for (index, item) in enumerate(s):
			if item in vowels:
				bitmaskrepr ^= vowels[item]
			if bitmaskrepr not in bitmask_to_index:
				bitmask_to_index[bitmaskrepr] = index
			else:
				result = max(result, index - bitmask_to_index[bitmaskrepr])
		return result


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		masks = {0: -1}
		mask = 0
		match = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		max_len = 0
		for (i, ch) in enumerate(s):
			if ch in match:
				mask = mask ^ 1 << match[ch]
			if mask in masks:
				max_len = max(max_len, i - masks[mask])
			else:
				masks[mask] = i
		return max_len


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = set('aeiou')
		odd = {tuple(): -1}
		key = tuple()
		res = 0
		window = collections.Counter()
		vowel_count = [window]
		for (i, char) in enumerate(s):
			if char in vowels:
				window[char] += 1
				key = tuple((c for c in window if window[c] & 1))
				if key in odd:
					res = max(i - odd[key], res)
				else:
					odd[key] = i
			else:
				res = max(i - odd[key], res)
		else:
			res = max(i - odd[key], res)
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		d = {0: -1}
		binRep = 0
		res = 0
		for (i, char) in enumerate(s):
			if char in vowels:
				binRep = binRep ^ vowels[char]
			if binRep not in d:
				d[binRep] = i
			else:
				res = max(res, i - d[binRep])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		(n, vowels, d) = (len(s), 'aeiou', {0: -1})
		ret = cur = 0
		for (i, c) in enumerate(s):
			if c in vowels:
				cur ^= 1 << vowels.index(c)
			d.setdefault(cur, i)
			ret = max(ret, i - d[cur])
		return ret


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		digits = {c: i for (i, c) in enumerate('aeiou')}
		ans = counter = 0
		seen = {0: -1}
		for (i, c) in enumerate(s):
			if c in digits:
				counter ^= 1 << digits[c]
			seen.setdefault(counter, i)
			ans = max(ans, i - seen[counter])
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		n = len(s)
		dp = {}
		for k in range(n, 0, -1):
			for i in range(0, n + 1 - k):
				if k == n:
					s_count = collections.Counter(s)
					dp[i, k] = [s_count.get(c, 0) % 2 == 0 for c in 'aeiou']
				elif i == 0:
					dp[i, k] = self.update_tracker(s[i + k], dp.get((i, k + 1)))
				else:
					dp[i, k] = self.update_tracker(s[i - 1], dp.get((i - 1, k + 1)))
				if all(dp[i, k]):
					return k
		return 0

	def update_tracker(self, char, tracker):
		idx = 'aeiou'.find(char)
		new_tracker = list(tracker)
		if idx > -1:
			new_tracker[idx] = not tracker[idx]
		return new_tracker


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		res = 0
		pos = {0: -1}
		state = 0
		vowels = 'aeiou'
		for i in range(len(s)):
			j = vowels.find(s[i])
			if j >= 0:
				state ^= 1 << j
			if state in pos:
				res = max(res, i - pos[state])
			else:
				pos[state] = i
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		(mask, seen, smax, vowels) = (0, {0: -1}, 0, {x: 1 << i for (i, x) in enumerate('aeiou')})
		for (i, x) in enumerate(s):
			if x in vowels:
				mask ^= 1 << vowels[x]
			seen.setdefault(mask, i)
			smax = max(smax, i - seen[mask])
		return smax


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		for window_size in range(len(s), -1, -1):
			end_pos = len(s) - window_size + 1
			for i in range(end_pos):
				substring = s[i:i + window_size]
				is_all_even = True
				for ch in 'aeiou':
					if substring.count(ch) % 2:
						is_all_even = False
						break
				if is_all_even:
					return window_size
		return 0


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		(state, statedict) = (0, {0: -1})
		voweldict = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		maxlen = 0
		for (i, c) in enumerate(s):
			if c in voweldict:
				state ^= voweldict[c]
			if state in statedict:
				maxlen = max(maxlen, i - statedict[state])
			else:
				statedict[state] = i
		return maxlen


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = 'aeiou'
		mask = last_mask = 0
		first = [-1] + [float('inf')] * 31
		last = [-1] + [float('-inf')] * 31
		for (i, c) in enumerate(s):
			if c in set(vowels):
				j = vowels.index(c)
				(last_mask, mask) = (mask, mask ^ 1 << j)
				if first[mask] == float('inf'):
					first[mask] = last[last_mask] + 1
			last[mask] = i
		return max((j - i for (i, j) in zip(first, last)))


VOWELS = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}

class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		seen = {0: -1}
		mask = 0
		longest = 0
		for (ind, char) in enumerate(s):
			mask ^= VOWELS.get(char, 0)
			if mask not in seen:
				seen[mask] = ind
			else:
				longest = max(longest, ind - seen[mask])
		return longest


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		substrings = self.generate_subst(s)
		res = 0
		for substring in substrings:
			is_all_even = True
			for ch in 'aeiou':
				if substring.count(ch) % 2:
					is_all_even = False
					break
			if is_all_even:
				return len(substring)
		return res

	def generate_subst(self, s: str):
		for window_size in range(len(s), -1, -1):
			for i in range(len(s) - window_size + 1):
				yield s[i:i + window_size]


from collections import defaultdict

class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		res = 0
		vowel_map = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
		visited = {0: -1}
		pattern = 0
		for (i, c) in enumerate(s):
			if c in vowel_map:
				pattern ^= 1 << vowel_map[c]
			if pattern not in visited:
				visited[pattern] = i
			res = max(res, i - visited[pattern])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		idx_dic = {0: -1}
		vowels = 'aeiou'
		state = ans = 0
		for i in range(len(s)):
			j = vowels.find(s[i])
			if j >= 0:
				state ^= 1 << j
			if state not in idx_dic:
				idx_dic[state] = i
			ans = max(ans, i - idx_dic[state])
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		state = 0
		d = {0: -1}
		vowels = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
		max_len = 0
		for i in range(len(s)):
			if s[i] in vowels:
				state ^= vowels[s[i]]
				if state not in d:
					d[state] = i
			if state in d:
				max_len = max(max_len, i - d[state])
		return max_len


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowels = 'aeiou'
		helper = {0: -1}
		state = 0
		res = 0
		for (i, ch) in enumerate(s):
			j = vowels.find(ch)
			if j >= 0:
				state ^= 1 << j
			if state not in helper:
				helper[state] = i
			res = max(res, i - helper[state])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		for i in range(len(s), -1, -1):
			for x in range(len(s) - i + 1):
				counter = 0
				temp = s[x:x + i]
				for k in 'aeiou':
					if temp.count(k) % 2 != 0:
						counter += 1
						break
				if counter == 0:
					return i


from collections import defaultdict

class Solution:

	def findTheLongestSubstring(self, string: str) -> int:
		vowels = 'aeiou'
		vowels_dict = dict(zip(vowels, range(5)))
		curr = 0
		pos_dict = defaultdict(lambda : float('inf'))
		pos_dict[0] = -1
		res = 0
		for (i, v) in enumerate(string):
			if v in vowels_dict:
				curr ^= 1 << vowels_dict[v]
			res = max(res, i - pos_dict[curr])
			pos_dict[curr] = min(pos_dict[curr], i)
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		digits = {c: i for (i, c) in enumerate('aeiou')}
		counters = [0]
		for c in s:
			if c in digits:
				counters.append(counters[-1] ^ 1 << digits[c])
			else:
				counters.append(counters[-1])
		for length in range(len(s), 0, -1):
			for j in range(len(s), length - 1, -1):
				if not counters[j] ^ counters[j - length]:
					return length
		return 0


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		d = {(0, 0, 0, 0, 0): -1}
		count = [0, 0, 0, 0, 0]
		pos = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
		ans = 0
		for (i, char) in enumerate(s):
			if char in pos:
				count[pos[char]] = (count[pos[char]] + 1) % 2
			t = tuple(count)
			if t in d:
				ans = max(ans, i - d[t])
			else:
				d[t] = i
		return ans


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		seen = {0: -1}
		pos = {c: i for (i, c) in enumerate('aeiou')}
		curr = res = 0
		for (i, c) in enumerate(s):
			curr ^= 1 << pos.get(c, -1) + 1 >> 1
			seen.setdefault(curr, i)
			res = max(res, i - seen[curr])
		return res


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		lu = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}

		def setFlags(flags: int, ch: str) -> int:
			if ch in lu.keys():
				mask = 1 << lu[ch]
				flags = flags ^ mask
			return flags
		FLAGS = 0
		seen = {0: -1}
		m = 0
		for (i, c) in enumerate(s):
			FLAGS = setFlags(FLAGS, c)
			if FLAGS in seen.keys():
				m = max(m, i - seen[FLAGS])
			else:
				seen[FLAGS] = i
		return m


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		masks = {'a': 16, 'e': 8, 'i': 4, 'o': 2, 'u': 1}
		num = 0
		numToIdx = {0: -1}
		ans = 0
		for (i, ch) in enumerate(s):
			if ch in masks:
				num ^= masks[ch]
			if num not in numToIdx:
				numToIdx[num] = i
			ans = max(ans, i - numToIdx[num])
		return ans


from copy import copy

class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		vowel2idx = dict([(item[1], item[0]) for item in enumerate(['a', 'e', 'i', 'o', 'u'])])
		counters = [[0] * len(vowel2idx)]
		for item in s:
			counters.append(counters[-1].copy())
			if item in vowel2idx:
				counters[-1][vowel2idx[item]] += 1
		for width in range(len(s), 0, -1):
			for start in range(len(s) - width + 1):
				for n_vowels in map(int.__sub__, counters[start + width], counters[start]):
					if n_vowels % 2 == 1:
						break
				else:
					return width
		return 0


class Solution:

	def findTheLongestSubstring(self, s: str) -> int:
		dp = [-1] + [len(s)] * 31
		mask = 0
		res = 0
		for (i, c) in enumerate(s):
			if c in 'aeiou':
				mask ^= 1 << 'aeiou'.index(c)
			dp[mask] = min(dp[mask], i)
			res = max(res, i - dp[mask])
		return res