<p>You are given a string <code>s</code>. An <strong>awesome</strong> substring is a non-empty substring of <code>s</code> such that we can make any number of swaps in order to make it a palindrome.</p>

<p>Return <em>the length of the maximum length <strong>awesome substring</strong> of</em> <code>s</code>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;3242415&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> &quot;24241&quot; is the longest awesome substring, we can form the palindrome &quot;24142&quot; with some swaps.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;12345678&quot;
<strong>Output:</strong> 1
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;213123&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> &quot;213123&quot; is the longest awesome substring, we can form the palindrome &quot;231132&quot; with some swaps.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists only of digits.</li>
</ul>

class Solution {
public:
    int longestAwesome(string s) {
        /*
        - awesome subst = non empty substr s.t. u can make any number of swaps to make it palindrome
        - ret max len awesome substr 
        - means u need <= 1 odd of all char cts
        
        - n^2 = go through each i,j and track odd cts in hashmap
        - u never know if u can move window left cuz there maybe valid palin chars later in string

        - save odd and evens only, need to make sure only <= 1 val w odd ct ... remove most outter idx till true 
        - just need to remove 1 of (all but 1) odd vals ... 
        ct: val: [idx]
        odd: {3, [0]}, {1, [5]}, {5, [6]} ... 3,1,5
        idx: 0,5,6 ... remove 6 first 
            - this means 0-4, 1-5, 5, 6 r all awesome palin
        - rem [6] ... now substr is [0]->[5]
        - rem either since both on opposite ends (other rem whichever keeps substr longer)
        
        12345678 
        odd (just need to know which vals): 1, 2, 3, 4, 5, 6, 7, 8
        idx (need idx of all odd vals): 0,1,2,3,4,5,6,7,8  ... no awsome palin (since no space btwn vals)
        - u want to erase whichever idx is closest to beginning or end
        - for each val i need to erase 1 idx
        - i also need to sort by idx to know which val to erase
        
        213123
        odd: [], means whole thing is a plain 

        - doesnt work cuz if 324243315 & i pop first 3, now next 3 r not part of odds.
        - for each val u decide to pop from odds, all other idx of that val are now part of palin

        ex.) 324243315 
        odds: 3: [0,5,6], 1: [7], 5: [8]
        odd_idx: 8=5, 7=1, 6=3, 5=3, 0=3
        - remove end (8) ... since its val is 5, rem that from odds and all idx for 5 from odd_idx ... l=0, r=7
        odds: 3: [0,5,6], 1: [7],
        odd_idx: 7=1, 6=3, 5=3, 0=3 .... which which idx results in larget string, both 0 and 7 r fine, use 0

        ex.)
        9498331
        odds: 4, 8, 1

        - issue: when i remove 4, that gets rid of front 9 so that becomes odd now
        
        - another option:
        - if max_len = 5, that means some palin must exist of size 4
        - if max_len = 4, means some palin must exist of size 3
        - find first m < n, where palin of size m exists, but not size m+1 ... log n
        - how much time to determine if palin of size m exists -> O(m)
        - doesnt work -- cuz palin of size 4 wont be in 1 substr, it can be broken by middle 5th element

        - only 1 val at most can have odd amnt
        - if (x & x-1) == 0 or x == 0 ... this substr is awesome
        - at each step, x ^= 1 << s[i]
        - 3,2,4,2,4
            - after 4, same mask as after 3 ... so we know that [2,4,2,4] is awesome palin

        - only when u see a mask u have alr seen, means u just went through a substr thats palin outside single diff char
        - so add 1 to this (for prev or next odd char?)

        - as we keep track of mask -- we check prev occur of max = p ... [p...i] is palin w/ all even
        - to check for max palin w/ 1 odd ... we need to check for all masks that differ by 1 bit (for any seen earlier)
        - this means, try to flip every bit (in for loop, so 1 bit at a time), and track min of prev seen for all these

        */  

        int n = s.size();
        int mask_options = pow(2, 10); // 10 dig
        vector<int> first_occur(mask_options + 1, -1); // [mask] = first idx after which u saw this mask
        first_occur[0] = -1; 
        int mask = 0;
        int max_len = 1;

        for (int i = 0; i < n; ++i) {
            int val = s[i] - '0';
            mask ^= 1 << val;

            // unseen mask --- means max palin inc this is 1 (for 1 odd)
            if (mask != 0 && first_occur[mask] == -1) {
                first_occur[mask] = i;
            } else {
                // check for 1 odd by flipping each bit
                max_len = max(max_len, i - first_occur[mask]); 
            }

            for (int b = 0; b < 10; b++) {
                int tmp = mask ^ 1 << b;
            
                // update max len ... tmp mask must have been seen
                if (tmp == 0 || first_occur[tmp] != -1) max_len = max(max_len, i - first_occur[tmp]);
            }
        }

        return max_len;
        
        // n log m
        // int n = s.size();
        // int l = 0, r = n-1;
        // while (l <= r) {
        //     int m = (l + r) / 2;
        //     int make_m = canMakeSubstr(s, m);
        //     int make_m1 = canMakeSubstr(s, m+1);
        //     if (make_m && !make_m1) {
        //         // m is max len
        //         return m;
        //     } else if (make_m && make_m1) {
        //         // can make larger
        //         l = m+1; 
        //     } else {
        //         r = m-1;
        //     }
        // }

        // return 1;

        // n -- didnt work
        // unordered_map<int, vector<int>> odds; // val -> all i where [i]=val
        // unordered_map<int, vector<int>> tmp;
        // map<int, int> odd_idx; // idx -> [idx]
        // for (int i = 0; i < s.size(); ++i) tmp[s[i] - '0'].push_back(i);
        
        // // keep only vals w odd # occur in 'odds' and put those into odd_idx
        // for (auto& entry : tmp) {
        //     if (entry.second.size() % 2 == 1) {
        //         for (int idx : entry.second) {
        //             odds[entry.first].push_back(idx);
        //             odd_idx[idx] = entry.first;
        //         }
        //     }
        // }

        // // now u keep removing vals off & update l,r till only 1 key in odds
        // int l = 0;
        // int r = s.size()-1;
        // while (odds.size() > 1) {
        //     int top_i = odd_idx.begin()->first;
        //     int bottom_i = odd_idx.rbegin()->first;

        //     // check which one makes str longer
        //     int rem_i = top_i;
        //     if (top_i - l > r - bottom_i) rem_i = bottom_i;

        //     // remove rem_i
        //     // cout << rem_i << " " << l << " " << r << endl;
        //     int val = s[rem_i] - '0';
        //     for (int idx : odds[val]) odd_idx.erase(idx);
        //     odds.erase(val);

        //     // update l,r 
        //     if (rem_i == top_i) {
        //         l = top_i + 1;
        //     } else {
        //         r = bottom_i - 1;
        //     }
        // }

        // return r-l+1;

        // n^2
        // int max_len = 1;
        // int n = s.size();
        // for (int i = 0; i < n; ++i) {
        //     string curr = "";
        //     int odd_ct = 0;
        //     unordered_map<char, int> char_cts;

        //     for (int j = i; j < n; ++j) {
        //         char c = s[j];
        //         if (char_cts[c] % 2 == 0) {
        //             odd_ct++;
        //         } else {
        //             odd_ct--;
        //         }
        //         char_cts[c]++;

        //         curr.push_back(c);
        //         if (odd_ct < 2) max_len = max(max_len, static_cast<int>(curr.size()));
        //     }
        // }

        // return max_len;
    }

    // 35
    bool canMakeSubstr(string& s, int m) {
        // track which elem have odd ct ... if size of set ever < 2 ... ret true
        int l = 0;
        int r = 0;
        unordered_set<int> odds;

        while (r < m) {
            int val = s[r] - '0';
            if (odds.find(val) == odds.end()) {
                odds.insert(val);
            } else {
                odds.erase(val);
            }
            r++;
        }
        if (odds.size() < 2) return true;

        while (r < s.size()) {
            // remove l & add r
            int val_l = s[l] - '0';
            int val_r = s[r] - '0';

            if (odds.find(val_l) == odds.end()) {
                odds.insert(val_l);
            } else {
                odds.erase(val_l);
            }

            if (odds.find(val_r) == odds.end()) {
                odds.insert(val_r);
            } else {
                odds.erase(val_r);
            }

            // now check if valid
            if (odds.size() < 2) return true;
            l++;
            r++;
        }

        return false;
    }
};
11300