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

/*
    // brute force - N^2
    answer = 0
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isVowel(s[j])) {
                freq[s[j]]++;
            }
            if (allVowelFreqEven(freq)) {
                answer = max(answer, j - i + 1);
            }
        }
    }
*/
/*
    for (int i = 0; i < n; i++) {
        if (isVowel(s[i])) {
            freq[s[i]]++;
            ans = 0
            for each vowel:
                if freq[vowel] == 0:
                    continue
                
                
        } else {

        }
    }
*/
class Solution {
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
    void temp(string s, int start_idx, int end_idx) {
        int freq[26] = {};
        cout << "\n";
        for (int i = start_idx; i <= end_idx; i++) {
            if (isVowel(s[i])) {
                freq[s[i] - 'a']++;
            }
        }

        vector<int> vowels({'a' - 'a', 'e' - 'a', 'i' - 'a', 'o' - 'a', 'u' - 'a'});
        for (int vowel_idx: vowels) {
            cout << freq[vowel_idx] << " ";
        }
    }
    int binarySearch(vector<int>& a, int val) {
        int left = 0, right = a.size() - 1, answer = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (a[mid] >= val) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
public:
    // space can be optimized
    int findTheLongestSubstring(string s) {
        int answer = 0;
        vector<int> occ[26];
        vector<int> vowels({'a' - 'a', 'e' - 'a', 'i' - 'a', 'o' - 'a', 'u' - 'a'});
        int final_idx = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s[i])) {
                occ[s[i] - 'a'].push_back(i);
            }
            int start_idx = 0;
            while (start_idx <= i) {
                int local_si = start_idx;
                for (int vowel_idx: vowels) {
                    // even case
                    if (occ[vowel_idx].size() == 0) {
                        continue;
                    } else {
                        int bs = binarySearch(occ[vowel_idx], start_idx);
                        // even case
                        if (bs == -1) {
                            continue;
                        }
                        int sz = occ[vowel_idx].size();
                        if ((sz - bs) & 1) {
                            local_si = max(local_si, occ[vowel_idx][bs] + 1);
                        }
                    }
                }
                if (start_idx == local_si) {
                    break;
                }
                start_idx = local_si;
            }
            int mx = i - start_idx + 1;
            if (mx > answer) {
                final_idx = i;
            }
            answer = max(answer, mx);
        }
        return answer;
    }
};
18300