<p>Given the string <code>s</code>, return the size of the longest substring containing each vowel an even number of times. That is, &#39;a&#39;, &#39;e&#39;, &#39;i&#39;, &#39;o&#39;, and &#39;u&#39; must appear an even number of times.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;eleetminicoworoep&quot;
<strong>Output:</strong> 13
<strong>Explanation: </strong>The longest substring is &quot;leetminicowor&quot; which contains two each of the vowels: <strong>e</strong>, <strong>i</strong> and <strong>o</strong> and zero of the vowels: <strong>a</strong> and <strong>u</strong>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetcodeisgreat&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> The longest substring is &quot;leetc&quot; which contains two e&#39;s.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bcbcbc&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> In this case, the given string &quot;bcbcbc&quot; is the longest because all vowels: <strong>a</strong>, <strong>e</strong>, <strong>i</strong>, <strong>o</strong> and <strong>u</strong> appear zero times.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 x 10^5</code></li>
	<li><code>s</code>&nbsp;contains only lowercase English letters.</li>
</ul>

"""
Approach: Bit mask and XOR

1. Assign a,e,i,o,u unique bits so that they cancel out to "0" if you xor each of them an even number of times
a = 1, e = 2, i = 4, o = 8, u = 16 (note that each one is a separate bit).
We can then treat other characters as "0".

2. Iterate through the string and get the mask (the prefix-XOR cumulative from index 0 to this index).

3. When we get a mask that we already discovered before, that means the substring[initialIndex:currentIndex] have even vowels.
This is because starting at a certain index of value say 10, we can only get back to 10 if the characters in this substring 
cancel out via XOR.
3a. Use a dictionary to track the first time a new mask occurs, so that we can use it to get the longest length possible.
That is distance = [current index] - [first time occurence index] + 1

4. Update the maximum distance and update it as we go

Ex1:
eleetminic  o w  o r o  e  p
2202226622 10 10 2 2 10 12 12 
  ^     ^ 
  2-0+1
        8-1+1
Ex2:

leetcod e  i   s  g  r  e  a  t
0200088 10 14  14 14 14 12 13  13
    ^
    4-0+1

Ex 4:
*amntyyaw
011111100

Need to add 0 at the start

100
010
---
110 = 10

let N = len(s)
Time: O(N)
We iterate through string s once
Space: O(N)
For firstOccurrence map. Worst case, each index is a first occurrence of a new mask.

Idea:
https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solutions/534135/c-java-with-picture/ 
https://www.youtube.com/watch?v=4Xl9Hh0M9aE&ab_channel=CodeThoughts 
"""

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        # Assign a,e,i,o,u unique bits so that they cancel out to "0" if you xor each of them an even number of times
        vowelMap = defaultdict(lambda: 0, a=1, e=2, i=4, o=8, u=16)
        
        # preset the first occurence of 0 to be -1 for cases like amntyyaw
        firstOccurrence = {0:-1}
        
        mask = 0
        maxDist = 0
        for idx in range(0,len(s)):
            letter = s[idx]
            mask ^= vowelMap[letter]

            dist = 0
            if mask not in firstOccurrence:
                firstOccurrence[mask] = idx
            else:
                # Actually don't need this, because we added a 0 at the front, which would automatically offset the +1
                # if firstOccurrence[mask] == 0 and vowelMap[s[0]]==0:
                #     # For non-vowels at the initial index, we also include the value at index=0
                #     dist = idx - firstOccurrence[mask] + 1
                # else:
                #     dist = idx - firstOccurrence[mask]
                dist = idx - firstOccurrence[mask]
                maxDist = max(dist,maxDist)
            #print("letter=",letter)
            #print("dist={},idx={},mask={},firstOccurrence[mask]={}".format(dist,idx,mask,firstOccurrence[mask]))
        #print("firstOccurrence: ",firstOccurrence)

        return maxDist

"""
"amntyyaw"
"""


22600