find_the_longest_substring_containing_vowels_in_even_counts
1from collections import defaultdict 2 3 4# @leet start 5class Solution: 6 def findTheLongestSubstring(self, s: str) -> int: 7 """ 8 This question asks us to find the longest substring where vowels have 9 an even count. The brute force way is to iterate through all the substrings 10 and maintain a vowel count while doing so, in $O(n^2)$ time. We can 11 however, do better. Since we only care about the parity of the vowels 12 we can use XOR to find this out in one pass, for $O(n)$ time. 13 14 To do so, we create a bitmask which is XORed into to figure out when 15 we've seen the same amount of even vowels again. 16 17 Say we create a mapping of: 18 a = 1 19 e = 2 20 i = 4 21 o = 8 22 u = 16 23 24 If we create a bitmask of these, and xor each character, we can save the 25 last time we've seen this particular bitmask. In that case, we know that 26 our vowel counts are even, since XOR takes care of that (all even counts 27 will XOR to 0). 28 29 So we just keep track of the last time we saw a bitmask, and then if we see 30 it again, we may have a longer substring, so we check that. 31 """ 32 start = {0: -1} 33 mask = 0 34 chars = defaultdict(int) | {c: 1 << i for i, c in enumerate("aeiou")} 35 res = 0 36 37 for i, c in enumerate(s): 38 mask ^= chars[c] 39 if mask in start: 40 res = max(res, i - start[mask]) 41 else: 42 start[mask] = i 43 return res 44 45 46# @leet end 47 48 49def test(): 50 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def findTheLongestSubstring(self, s: str) -> int: 8 """ 9 This question asks us to find the longest substring where vowels have 10 an even count. The brute force way is to iterate through all the substrings 11 and maintain a vowel count while doing so, in $O(n^2)$ time. We can 12 however, do better. Since we only care about the parity of the vowels 13 we can use XOR to find this out in one pass, for $O(n)$ time. 14 15 To do so, we create a bitmask which is XORed into to figure out when 16 we've seen the same amount of even vowels again. 17 18 Say we create a mapping of: 19 a = 1 20 e = 2 21 i = 4 22 o = 8 23 u = 16 24 25 If we create a bitmask of these, and xor each character, we can save the 26 last time we've seen this particular bitmask. In that case, we know that 27 our vowel counts are even, since XOR takes care of that (all even counts 28 will XOR to 0). 29 30 So we just keep track of the last time we saw a bitmask, and then if we see 31 it again, we may have a longer substring, so we check that. 32 """ 33 start = {0: -1} 34 mask = 0 35 chars = defaultdict(int) | {c: 1 << i for i, c in enumerate("aeiou")} 36 res = 0 37 38 for i, c in enumerate(s): 39 mask ^= chars[c] 40 if mask in start: 41 res = max(res, i - start[mask]) 42 else: 43 start[mask] = i 44 return res
def
findTheLongestSubstring(self, s: str) -> int:
7 def findTheLongestSubstring(self, s: str) -> int: 8 """ 9 This question asks us to find the longest substring where vowels have 10 an even count. The brute force way is to iterate through all the substrings 11 and maintain a vowel count while doing so, in $O(n^2)$ time. We can 12 however, do better. Since we only care about the parity of the vowels 13 we can use XOR to find this out in one pass, for $O(n)$ time. 14 15 To do so, we create a bitmask which is XORed into to figure out when 16 we've seen the same amount of even vowels again. 17 18 Say we create a mapping of: 19 a = 1 20 e = 2 21 i = 4 22 o = 8 23 u = 16 24 25 If we create a bitmask of these, and xor each character, we can save the 26 last time we've seen this particular bitmask. In that case, we know that 27 our vowel counts are even, since XOR takes care of that (all even counts 28 will XOR to 0). 29 30 So we just keep track of the last time we saw a bitmask, and then if we see 31 it again, we may have a longer substring, so we check that. 32 """ 33 start = {0: -1} 34 mask = 0 35 chars = defaultdict(int) | {c: 1 << i for i, c in enumerate("aeiou")} 36 res = 0 37 38 for i, c in enumerate(s): 39 mask ^= chars[c] 40 if mask in start: 41 res = max(res, i - start[mask]) 42 else: 43 start[mask] = i 44 return res
This question asks us to find the longest substring where vowels have an even count. The brute force way is to iterate through all the substrings and maintain a vowel count while doing so, in $O(n^2)$ time. We can however, do better. Since we only care about the parity of the vowels we can use XOR to find this out in one pass, for $O(n)$ time.
To do so, we create a bitmask which is XORed into to figure out when we've seen the same amount of even vowels again.
Say we create a mapping of: a = 1 e = 2 i = 4 o = 8 u = 16
If we create a bitmask of these, and xor each character, we can save the last time we've seen this particular bitmask. In that case, we know that our vowel counts are even, since XOR takes care of that (all even counts will XOR to 0).
So we just keep track of the last time we saw a bitmask, and then if we see it again, we may have a longer substring, so we check that.
def
test():