<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>

class Solution:
    def findTheLongestSubstring_(self, s: str) -> int:
        vowels = 'aeiou'
        vid = dict(zip(vowels, map(lambda ch: ord(ch) - ord('a'), vowels)))
        vowels = set(vowels)
        ps = [0]
        for ch in s:
            if ch not in vowels:
                ps.append(ps[-1])
            else:
                ps.append(ps[-1] ^ (1<<vid[ch]))
        stat = defaultdict(list)
        for i, s in enumerate(ps):
            stat[s].append(i)
        ans = 0
        for v in stat.values():
            ans = max(ans, v[-1]-v[0])
        return ans    

    def findTheLongestSubstring(self, s: str) -> int:
        first_index = [-2] * 32
        last_index = [-2] * 32

        masks = {'a':1, 'e':2, 'i':4, 'o': 8, 'u': 16}
        mask = 0
        first_index[0] = -1
        for i, ch in enumerate(s):
            if ch in 'aeiou':
                mask ^= masks[ch]
            if first_index[mask] == -2:
                first_index[mask] = i
            last_index[mask] = i

        return max(l - f for f, l in zip(first_index, last_index))


    def findTheLongestSubstring2(self, s: str) -> int:
        a_sum = [0] * (len(s) + 1)
        e_sum = [0] * (len(s) + 1)
        i_sum = [0] * (len(s) + 1)
        o_sum = [0] * (len(s) + 1)
        u_sum = [0] * (len(s) + 1)

        for i, ch in enumerate(s):
            a_sum[i+1] = a_sum[i]
            e_sum[i+1] = e_sum[i]
            i_sum[i+1] = i_sum[i]
            o_sum[i+1] = o_sum[i]
            u_sum[i+1] = u_sum[i]

            if ch == 'a':
                a_sum[i+1] += 1
            elif ch == 'e':
                e_sum[i+1] += 1
            elif ch == 'i':
                i_sum[i+1] += 1
            elif ch == 'o':
                o_sum[i+1] += 1
            elif ch == 'u':
                u_sum[i+1] += 1

        def is_valid(l):
            for i in range(0, len(s) - l + 1):
                start, end = i, i + l
                if (a_sum[end] - a_sum[start]) % 2 == 0 and (e_sum[end] - e_sum[start]) % 2 == 0 and (i_sum[end] - i_sum[start]) % 2 == 0 and (o_sum[end] - o_sum[start]) % 2 == 0 and (u_sum[end] - u_sum[start]) % 2 == 0:
                    return True
            return False

        print(len(s))
        for l in range(len(s), -1, -1):
            if is_valid(l):
                return l



    def findTheLongestSubstring1(self, s: str) -> int:
        debug = False
        a_sum = [0] * (len(s) + 1)
        e_sum = [0] * (len(s) + 1)
        i_sum = [0] * (len(s) + 1)
        o_sum = [0] * (len(s) + 1)
        u_sum = [0] * (len(s) + 1)

        a_next = [-1] * len(s)
        e_next = [-1] * len(s)
        i_next = [-1] * len(s)
        o_next = [-1] * len(s)
        u_next = [-1] * len(s)

        a_prev = [-1] * len(s)
        e_prev = [-1] * len(s)
        i_prev = [-1] * len(s)
        o_prev = [-1] * len(s)
        u_prev = [-1] * len(s)

        for i, ch in enumerate(s):
            a_sum[i+1] = a_sum[i]
            e_sum[i+1] = e_sum[i]
            i_sum[i+1] = i_sum[i]
            o_sum[i+1] = o_sum[i]
            u_sum[i+1] = u_sum[i]

            if ch == 'a':
                a_sum[i+1] += 1
                a_next[i] = i
                a_prev[i] = i
            elif ch == 'e':
                e_sum[i+1] += 1
                e_next[i] = i
                e_prev[i] = i
            elif ch == 'i':
                i_sum[i+1] += 1
                i_next[i] = i
                i_prev[i] = i
            elif ch == 'o':
                o_sum[i+1] += 1
                o_next[i] = i
                o_prev[i] = i
            elif ch == 'u':
                u_sum[i+1] += 1
                u_next[i] = i
                u_prev[i] = i


        def fill_next(arr):
            last = -1
            for i in range(len(s)-1, -1, -1):
                if arr[i] != -1:
                    last = arr[i]
                else:
                    arr[i] = last
        
        fill_next(a_next)
        fill_next(e_next)
        fill_next(i_next)
        fill_next(o_next)
        fill_next(u_next)

        def fill_prev(arr):
            prev = -1
            for i in range(len(s)):
                if arr[i] != -1:
                    prev = arr[i]
                else:
                    arr[i] = prev
        
        fill_prev(a_prev)
        fill_prev(e_prev)
        fill_prev(i_prev)
        fill_prev(o_prev)
        fill_prev(u_prev)

        if debug:
            print("a_sum", a_sum)
            print("e_sum", e_sum)
            print("i_sum", i_sum)
            print("o_sum", o_sum)
            print("u_sum", u_sum)
        memo = {}
        def recursive(start, end):
            key = (start, end)
            if key in memo:
                return memo[key]
            if start > end:
                return 0
            if end == start:
                return 0 if s[end] in 'aeiou' else 1

            arr, arr_next, arr_prev = None, None, None
            arr_d = ''
            if (a_sum[end+1] - a_sum[start]) % 2 != 0:
                arr = a_sum
                arr_next = a_next
                arr_prev = a_prev
                arr_d = 'a'
            elif (e_sum[end+1] - e_sum[start]) % 2 != 0:
                arr = e_sum
                arr_next = e_next
                arr_prev = e_prev
                arr_d = 'e'
            elif (i_sum[end+1] - i_sum[start]) % 2 != 0:
                arr = i_sum
                arr_next = i_next
                arr_prev = i_prev
                arr_d = 'i'
            elif (o_sum[end+1] - o_sum[start]) % 2 != 0:
                arr = o_sum
                arr_next = o_next
                arr_prev = o_prev
                arr_d = 'o'
            elif (u_sum[end+1] - u_sum[start]) % 2 != 0:
                arr = u_sum
                arr_next = u_next
                arr_prev = u_prev
                arr_d = 'u'
            
            if arr is None:
                memo[key] = end - start + 1
            else:
                # l_pos = bisect.bisect_left(arr, arr[start] + 1) - 1
                # r_pos = bisect.bisect_right(arr, arr[end+1] - 1) - 1
                l_pos, r_pos = arr_next[start], arr_prev[end]

                if debug:
                    print(f"start={start}, end={end}, l_pos={l_pos}, r_pos={r_pos}, arr={arr_d}")

                if arr[end+1] - arr[start] == 1:
                    memo[key] = max( recursive(start, l_pos - 1), recursive(l_pos+1, end))
                else:
                    memo[key] = max( recursive(start, l_pos - 1), recursive(l_pos+1, end), recursive(start, r_pos -1), recursive(r_pos+1, end) )

            return memo[key]

        return recursive(0, len(s) - 1)


        

    def findTheLongestSubstring0(self, s: str) -> int:
        # eleetminicoworoep
        # e:0,2,3,15
        # i:6,8
        # o:10,12,14
        # e:4, i:2, o:3,

        # leetcodeisgreat
        # e:1,2,7
        # o:5
        # i:8
        # a:13
        # e:3, o:1, i:1, a:1
        vowels = defaultdict(list)
        for i, ch in enumerate(s):
            if ch in 'aeiou':
              vowels[ch].append(i)

        print(vowels)
        memo = {}
        def recursive(start, end):
            key = (start, end)
            if key in memo:
                return memo[key]
            if start > end:
                return 0
            if end == start:
                return 0 if s[end] in 'aeiou' else 0

            for vowel in vowels.keys():
                positions = vowels[vowel]
                l_ind = bisect.bisect_left(positions, start)
                r_ind = bisect.bisect_right(positions, end)

                if (r_ind - l_ind) % 2 == 0:
                    continue

                l_pos, r_pos = vowels[vowel][l_ind], vowels[vowel][r_ind-1]
                if r_ind - l_ind == 1:
                    memo[key] = max( recursive(start, l_pos - 1), recursive(l_pos+1, end))
                    return memo[key]
                
                # print(f"start={start}, end={end}, l_ind={l_ind}, r_ind={r_ind}, vowel={vowel}, l_pos={l_pos}, r_pos={r_pos}")

                # start, l_pos - 1
                # l_pos +1, end
                # start, r_pos - 1
                # r_pos +1, end

                memo[key] = max( recursive(start, l_pos - 1), recursive(l_pos+1, end), recursive(start, r_pos -1), recursive(r_pos+1, end) )
                return memo[key]
            
            memo[key] = end - start + 1
            return memo[key]

        return recursive(0, len(s) - 1)

125