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

#define CountSetBits __builtin_popcount
#define nl cout<<"\n"
int ctoi(char c){
    return c-'0';
}

class Solution {
public:
    int longestAwesome(string s) {
        /*
            prefix arr, pre[i] = s[0:i] = freq parity(even or odd freq) of digits 0-9
            if pre[i]==0 or has only 1 set bit, means s[0:i] is awesome, ans=i+1
            
            pre[i] ^ pre[j] == x == 0 or 1 set bit
            pre[i] ^ x == pre[j], loop on x=[2^0, 2^10], x<<=1
            
            xor table
            0 ^ 0 = 0
            0 ^ 1 = 1
            1 ^ 0 = 1
            1 ^ 1 = 0
        */


        int cur=0, n = s.size();
        unordered_map<int, int> preMap; auto&m=preMap;// map[val] -> ind
        vector<int> pre(n); 
        for(int i=0; i<n; i++){
            auto c = s[i];
            int x = ctoi(c);
            cur ^= (1<<x);

            if(preMap.find(cur) == preMap.end())
                preMap[cur] = i;
            pre[i] = cur;
        }

        int ans=0; 
        for(int i=0; i<n; i++){
            if(pre[i] == 0 or CountSetBits(pre[i])==1){
                ans = i+1;
            }else{
                if(m.find(pre[i]) != m.end()){
                    int j = preMap[pre[i]];
                    ans = max(ans, i-j);
                    if(ans%2==0) ans++;
                }
                int x = 1; 
                while(x <= 512){
                    int xorr = pre[i]^x;
                    if(preMap.find(xorr) != preMap.end()){
                        int j = preMap[xorr];                        
                        ans = max(ans, i-j);
                    }
                    x <<= 1;
                }
            }
        }

        return ans;
    }
};
15900