Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.
Return the length of the maximum length awesome substring of s.
 
Example 1:
Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:
Input: s = "12345678"
Output: 1

Example 3:
Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:
Input: s = "00"
Output: 2

 
Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Difficulty: interview

Starter code:

class Solution:
    def longestAwesome(self, s: str) -> int:
        

Solutions:
class Solution:
    def longestAwesome(self, s: str) -> int:
        cum = [0]
        firsts = {0: -1}
        lasts = {0: -1}
        for i, c in enumerate(s):
            cum.append(cum[-1] ^ (1 << (ord(c) - 48)))
            if cum[-1] not in firsts:
                firsts[cum[-1]] = i
            lasts[cum[-1]] = i
        mx = 1
        for k in firsts:
            mx = max(mx, lasts[k] - firsts[k])
            for off in range(10):
                o = k ^ (1 << off)
                if o in firsts:
                    mx = max(mx, lasts[o] - firsts[k])
        return mx

class Solution:
    def longestAwesome(self, s: str) -> int:
        #since transp. generate symm. grp., just need pair counts
        mask = 0
        prefix, suffix = {0 : -1}, {0 : -1}
        digcodes = [2**i for i in range(10)]+[0]
        
        for i in range(len(s)):
            ch = s[i]
            mask ^= 2**int(ch)
            if mask not in prefix:
                prefix[mask] = i
            suffix[mask] = i
        
        return max([ind - prefix[val ^ dig] for val,ind in list(suffix.items()) 
                    for dig in digcodes if val ^ dig in prefix])
        
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        d = {}
        d[0] = -1
        sm, res = 0, 0
        for i,c in enumerate(s):
            sm ^= 1 << int(c)
            if sm in d:
                res = max(res, i - d[sm])
            else:
                d[sm] = i
            for j in range(10):
                msk = sm ^ (1 << j)
                if msk in d and i - d[msk] > res:
                    res = i - d[msk]
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        n=len(s)
        
        a=0
        ans=0
        dp={0:-1}
        
        for i in range(n):
            a=a^(1<<(int(s[i])))
            
            if a in dp:
                ans=max(ans,i-dp[a])
            else:
                dp[a]=i
                
            for j in range(11):
                x=(a^(1<<j))
                if x in dp:
                    ans=max(ans,i-dp[x])
                
            #print(a,dp,i,ans)
        
        return ans


class Solution:
    def longestAwesome(self, s: str) -> int:
        known_positions = {0: -1}

        mask = 0
        max_size = 0

        for idx, current in enumerate(s):
            mask ^= 1 << (ord(current) - ord('0'))

            for modified in range(10):
                tmp_mask = mask ^ (1 << modified)
                size = idx - known_positions.get(tmp_mask, idx)

                if size % 2:
                    max_size = max(max_size, size)

            max_size = max(max_size, idx - known_positions.get(mask, idx))    
            known_positions.setdefault(mask, idx)

        return max(max_size, 1)

class Solution:
    def longestAwesome(self, s: str) -> int:
        memo = {0: -1}
        best = 0
        bitmap = 0
        for i, digit in enumerate(s):
            bitmap ^= 1 << int(digit)

            best = max(best, i - memo.get(bitmap, i))
            
            for j in range(10):
                key = bitmap ^ (1 << j)
                best = max(best, i - memo.get(key, i))
            memo[bitmap] = memo.get(bitmap, i)

        return best

class Solution:
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - 48)
            for j in range(11):
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res    

class Solution:
    def longestAwesome(self, s: str) -> int:
        pos = {0 : -1}
        bitmask = 0
        ans = 0
        n = len(s)
        for i in range(n):
            bitmask ^= (1 << int(s[i]))
            for j in range(10):
                if bitmask ^ (1 << j) in pos:
                    ans = max(ans, i - pos[bitmask ^ (1 << j)])
            if bitmask in pos:
                ans = max(ans, i - pos[bitmask])
            else:
                pos[bitmask] = i
            
        return ans

class Solution:
    def linear(self, s):
        ans = 0
        d = {0:-1}
        mask = 0
        for i, c in enumerate(s):
            mask = (1<<int(c)) ^ mask
            
            if mask in d:
                ans = max(ans, i - d[mask])
            
            for j in range(10):
                s = mask ^ (1<<j)
                if s in d:
                    ans = max(ans, i - d[s])
            
            if mask not in d:
                d[mask] = i
        return ans
    
    
        
        
    def longestAwesome(self, s: str) -> int:
        return self.linear(s)
    
        ans = 0
        for i in range(len(s)):
            d = collections.defaultdict(int)
            odds = set()
            for j in range(i, len(s)):
                d[s[j]]+=1
                if d[s[j]]%2:
                    odds.add(s[j])
                else:
                    if s[j] in odds:
                        odds.remove(s[j])
                
                if len(odds)<=1:
                    ans = max(ans, j-i+1)
        return ans
    
    
    
    
    
    
    
    
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        pos = {}
        open_chars = 0
        pos[open_chars] = 0
        max_len = 0
        for i, c in enumerate(s):
            open_chars ^= 1 << int(c)
            for j in range(-1, 10):
                if j == -1:
                    mask = 0
                else:
                    mask = 1 << j
                if open_chars ^ mask in pos:
                    max_len = max(max_len, i+1 - pos[open_chars ^ mask])
            
            if open_chars not in pos:
                pos[open_chars] = i+1
        return max_len
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        a = [0 for _ in range(n)]
        for i in range(n):
            x = a[i-1] if i > 0 else 0
            a[i] = x ^ (1 << int(s[i]))
        
        dp = 1
        ht = {}
        ht[a[0]] = 0
        
        for i in range(1, n):
            d = 1
            if a[i] == 0:
                d = i+1
            else:
                if a[i] in ht:
                    d = max(d, i-ht[a[i]])
                for j in range(10):
                    x = a[i] ^ (1 << j)
                    if x == 0:
                        d = i+1
                        break
                    if x in ht:
                        d = max(d, i-ht[x])

            dp = max(dp, d)
            if not a[i] in ht:
                ht[a[i]] = i
        
        return dp
        
            
        
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        index = [-1] + [len(s)]*1023
        ans = 0
        bit = 0
        for idx, c in enumerate(s):
            bit ^= 1 << ord(c)-ord('0')
            # if bit in index:
            #     ans = max(ans, idx-index[candidate])
            # else:
            #     index[bit]=idx
            # for i in range(10):
            #     candidate = bit^(1<<i)
            #     if candidate in index:
            #         ans = max(ans, idx-index[candidate])
            ans = max([ans, idx-index[bit]]+[idx-index[bit^(1<<j)] for j in range(10)])
            index[bit] = min(index[bit], idx)
        return ans

class Solution1:
    def longestAwesome(self, s: str) -> int:
        mem = {} 
        def find_awesome(lo, hi, digit_count):
            if lo > hi:
                return 0
            if (lo, hi) in mem:
                return mem[(lo, hi)]
                    
            if digit_count & (digit_count - 1) == 0:
                return hi - lo + 1
            
            max_len = max(find_awesome(lo + 1, hi, digit_count^((1 << int(s[lo])))),
                       find_awesome(lo, hi - 1, digit_count^((1 << int(s[hi])))))
            mem[(lo, hi)] = max_len
            return max_len
        
        lo, hi, digit_count = 0, len(s) - 1, 0
        for i in range(lo, hi + 1):
            digit_count ^= (1 << int(s[i]))
        return find_awesome(lo, hi, digit_count)
    
class Solution:
    def longestAwesome(self, s: str) -> int:
        memo, state = {}, 0
        memo[state], ans = -1, 0
        for i, c in enumerate(s):            
            state ^= 1 << int(c)                        
            if state not in memo:
                memo[state] = i
            else:
                ans = max(ans, i - memo[state])                            
            for j in range(10):
                state1 = state ^ (1 << j)                                 
                if state1 in memo:
                    ans = max(ans, i - memo[state1])
        return ans

#bd = binary dict
#soen = sum of each number
class Solution:
    
    def longestAwesome(self, s: str) -> int:
        # generate list of existing binaries
        bd = {}
        bd[0] = -1 # remember when searching start from index -1
        #soen = [0 for i in range(10)]
        soen = 0
        
        for i,n in enumerate(s): # first loop
            #binary operation
            soen ^= 1<<int(n)
            bd[soen] = -1
        
            # update dictionary with the latest index that can form awesome string
            bd[soen] = i
            for j in range(10):
                soen_cpy = soen
                soen_cpy ^=1<<j
                if soen_cpy in bd:
                    bd[soen_cpy] = i 
        
        soen = 0
        max_ = bd[0]+1
        for i,n in enumerate(s):
            soen ^= 1<<int(n)
            cur_max = bd[soen] - i
            if cur_max>max_:
                max_ = cur_max
        return max_


class Solution:
    def longestAwesome(self, s: str) -> int:
        idx = [-1] + [len(s)] * 1023
        ans, mask = 0, 0
        for i, c in enumerate(s):
            update = ord(c) - ord('0')
            mask ^= 1 << update
            ans = max(ans, i - idx[mask])
            for j in range(10):
                ans = ans = max(ans, i - idx[mask ^ (1 << j)])
            idx[mask] = min(idx[mask], i)
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        # alex wice solution
        P = [0]
        for c in s:
            x= int(c)
            P.append(P[-1])
            P[-1]^= 1<<x
            
            
        dict = {}
        valid = {1<<x for x in range(10)}
        valid.add(0)
        ans = 0
        
        for j,q in enumerate(P):
            for target in valid:
                i = dict.get(q^target,None)
                if i is not None:
                    ans = max(ans,j-i)
                    
                dict.setdefault(q,j)
                
        return(ans)

class Solution:
    def longestAwesome(self, s: str) -> int:
        d = {}
        d[0] = -1
        mask = 0
        ans = 0
        for i, ch in enumerate(s):
            mask ^= 1<<int(ch)
            if mask in d and (i-d[mask])%2 == 0:
                ans = max(ans, i-d[mask])
            for j in range(10):
                mask_edit = mask^(1<<j)
                if mask_edit in d and (i-d[mask_edit])%2 == 1:
                    ans = max(ans, i-d[mask_edit])
            if mask not in d:
                d[mask] = i
        return ans

class Solution:
\tdef longestAwesome(self, s: str) -> int:
\t\tseen = {0: -1}
\t\tcurrent_xor = 0
\t\tanswer = 1
\t\tn = len(s)
\t\txor_list = {0: 1, 1: 2, 2: 4, 3: 8, 4: 16, 5: 32, 6: 64, 7: 128, 8: 256, 9: 512}
\t\tfor i in range(n):
\t\t\tcurrent_xor ^= xor_list[int(s[i])]
\t\t\tif current_xor not in seen:
\t\t\t\tseen[current_xor] = i
\t\t\telse:
\t\t\t\tanswer = max(answer, i - seen[current_xor])
\t\t\tfor j in range(10):
\t\t\t\tnew_xor = current_xor ^ xor_list[j]
\t\t\t\tif new_xor in seen:
\t\t\t\t\tanswer = max(answer, i - seen[new_xor])
\t\treturn answer

class Solution:
    def longestAwesome(self, s: str) -> int:
        tmp = 0
        pos_map = {0: -1}
        ans = 1
        for i in range(len(s)):
            tmp ^= (1 << int(s[i]))
            if tmp in pos_map:
                ans = max(ans, i - pos_map[tmp])
            for x in range(10):
                another_tmp = tmp ^ (1 << x)
                if another_tmp in pos_map:
                    ans = max(ans, i - pos_map[another_tmp])
            if tmp not in pos_map:
                pos_map[tmp] = i
        return ans        

class Solution:
    def longestAwesome(self, s: str) -> int:
        memo, state = {}, 0
        memo[state], ans = -1, 0
        for i, c in enumerate(s):            
            state ^= 1 << int(c)                        
            if state not in memo: memo[state] = i
            else: ans = max(ans, i - memo[state])                            
            for n in range(10):
                state1 = state ^ (1 << n)                                 
                if state1 in memo: ans = max(ans, i - memo[state1])
        return ans  

class Solution:
    def longestAwesome(self, s):
        res, cur, n = 0, 0, len(s)
        seen = [-1] + [n] * 1024
        for i, c in enumerate(s):
            cur ^= 1 << int(c)
            for a in range(10):
                res = max(res, i - seen[cur ^ (1 << a)])
            res = max(res, i - seen[cur])
            seen[cur] = min(seen[cur], i)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        p = [0]
        for c in s:
            x = int(c)
            p.append(p[-1])
            p[-1] ^= 1 << x

        first = {}
        valid = {1 << x for x in range(10)}
        valid.add(0)

        res = 0
        for j, pj in enumerate(p):
            for target in valid:
                i = first.get(pj ^ target, None)
                if i is not None:
                    res = max(res, j - i)
            first.setdefault(pj, j)
        return res
    


class Solution:
    def longestAwesome(self, s):
            res, cur, n = 0, 0, len(s)
            seen = [-1] + [n] * 1024
            for i, c in enumerate(s):
                cur ^= 1 << int(c)
                for a in range(10):
                    res = max(res, i - seen[cur ^ (1 << a)])
                res = max(res, i - seen[cur])
                seen[cur] = min(seen[cur], i)
            return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        d = {0: -1}
        b = 0
        m = 0
        for i, c in enumerate(s):
            b ^= 1 << int(c)
            if not b or not(b & b-1):
                m = max(m, i-d.get(b, i-1), i+1)
                if not b:
                    h = 1
                    for _ in range(10):
                        m = max(m, i-d.get(h, i-1))
                        h <<= 1
            else:
                m = max(m, i-d.get(b, i-1))
                h = 1
                for _ in range(10):
                    if h & b:
                        m = max(m, i-d.get((~h) & b, i-1))
                    else:
                        m = max(m, i-d.get(h + b, i-1))
                    h <<= 1
            if b not in d:
                d[b] = i
        return m

class Solution:
    def longestAwesome(self, s: str) -> int:
        prev = [-1] + [len(s)] * 1024
        best = 1
        mask = 0
        for i in range(len(s)):
            mask ^= 1 << int(s[i])
            # print(i, bin(mask))

            for j in range(10):
                tmp = mask ^ (1 << j)
                if best < i - prev[tmp] + 1:
                    # print('- ' + bin(tmp), i, prev[tmp])
                    best = max(best, i - prev[tmp])
                # best = max(best, i - prev[tmp])

            best = max(best, i - prev[mask])
            prev[mask] = min(prev[mask], i)
        return best
                    


class Solution:
    def longestAwesome(self, s: str) -> int:
        res, cur, n = 0, 0, len(s)
        seen = [-1] + [n] * 1024
        for i, c in enumerate(s):
            cur ^= 1 << int(c)

            for a in range(10):
                res = max(res, i - seen[cur ^ (1 << a)])
            res = max(res, i - seen[cur])
            seen[cur] = min(seen[cur], i)
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        d = {0: -1}
        m = b = 0
        for i, c in enumerate(s):
            b ^= 1 << int(c)
            m = max(m, i-d.get(b, i-1))
            h = 1
            for _ in range(10):
                m = max(m, i-d.get((~h) & b if h & b else h + b, i-1))
                h <<= 1
            d.setdefault(b, i)
        return m

class Solution:
    def longestAwesome(self, s: str) -> int:
        
        def getMatchingMasks(mask):
            st = set([mask])
            
            for i in range(10):
                st.add(mask ^ (1 << i))
            
            return st
        
        mask = 0
        
        maskDict = dict()
        
        maskDict[0] = -1
        
        ans = 0
        for idx, ch in enumerate(s):
            digitVal = int(ch)
            
            mask ^= (1 << digitVal)
            
            for match in getMatchingMasks(mask):
                if match in maskDict:
                    ans = max(ans, idx - maskDict[match])
            
            if mask not in maskDict:
                # only record the first position
                maskDict[mask] = idx
        
        return ans

class Solution:
    def linear(self, s):
        ans = 0
        d = {0:-1}
        mask = 0
        for i, c in enumerate(s):
            mask = (1<<int(c)) ^ mask
            
            if mask in d:
                ans = max(ans, i - d[mask])
            
            for j in range(10):
                s = mask ^ (1<<j)
                if s in d:
                    ans = max(ans, i - d[s])
            
            if mask not in d:
                d[mask] = i
        return ans
    
    
        
        
    def longestAwesome(self, s: str) -> int:
        return self.linear(s)
    
        ans = 0
        for i in range(len(s)):
            d = collections.defaultdict(int)
            odds = set()
            for j in range(i, len(s)):
                d[s[j]]+=1
                if d[s[j]]%2:
                    odds.add(s[j])
                else:
                    if s[j] in odds:
                        odds.remove(s[j])
                
                if len(odds)<=1:
                    ans = max(ans, j-i+1)
        return ans
    
    
    
    
    
    
    
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        '''
        \"3242415\"
        
          9876543210
        0:0000000000    #ith digit is odd
        1:0000001000
        2:0000001100
        3:0000011100
        4:0000011000
        5:0000001000
        6:0000001010
        7:0000101010
        
        
        2: need 0000001100, 0000001101, 0000001110, ...
            add 0000001100
        '''
        digit_cnt = [0 for _ in range(len(s)+1)]
        for i in range(1,len(s)+1):
            digit_cnt[i] = digit_cnt[i-1] ^ (1<<int(s[i-1]))
        # print(digit_cnt)
        
        res = 1
        indx = {}
        indx[0] = 0
        for i in range(1, len(digit_cnt)):
            if digit_cnt[i] == 0: 
                res = max(res, i)
                continue
            for d in range(10):
                if digit_cnt[i] ^ (1<<d) in list(indx.keys()):
                    res = max(res, i-indx[digit_cnt[i] ^ (1<<d)])
            if not digit_cnt[i] in list(indx.keys()):
                indx[digit_cnt[i]] = i
        # print(indx)
        return res
        
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        d = {0: -1}
        b = 0
        m = 0
        for i, c in enumerate(s):
            b ^= 1 << int(c)
            m = max(m, i-d.get(b, i-1))
            h = 1
            for _ in range(10):
                if h & b:
                    m = max(m, i-d.get((~h) & b, i-1))
                else:
                    m = max(m, i-d.get(h + b, i-1))
                h <<= 1
            if b not in d:
                d[b] = i
        return m

class Solution:
    def longestAwesome(self, s: str) -> int:
        # n = len(s)
        # length = n
        # while length > 1:
        #     # exam medium
        #     start = 0
        #     end = start + length
        #     check = 0
        #     while end <= n:
        #         sub_s = s[start:end]
        #         tmp = {}
        #         for char in sub_s:
        #             if char not in tmp:
        #                 tmp[char] = 1
        #             else:
        #                 tmp[char] += 1 
        #         value = [a for a in list(tmp.values()) if a%2==1]
        #         if len(value) <= 1:
        #             check = 1
        #             break
        #         start += 1
        #         end += 1
        #     if check == 1:
        #         return length
        #     else:
        #         length -= 1
        # return 1
        n = len(s)
        ans = 0
        record = {}
        record[0] = -1
        bit = 0
        for i in range(n):
            bit = bit ^ (2**int(s[i]))
            if bit in record:
                ans = max(ans,i-record[bit])
            else:
                record[bit] = i
            for j in range(10):
                new_bit = bit ^ (2**j)
                if new_bit in record:
                    ans = max(ans,i-record[new_bit])
        return ans
        
#         n = len(s)
#         ans, mask = 0, 0
        
#         memo = [n] * 1024
#         memo[0] = -1
        
#         for i in range(n):
#             mask ^= 2**int(s[i])
\t\t\t
# \t\t\t# Case 1. Check if we have seen similar mask
#             ans = max(ans, i - memo[mask])
            
# \t\t\t# Case 2. Check for masks that differ by one bit
#             for j in range(10):
#                 test_mask = mask ^ (2**j)
#                 ans = max(ans, i - memo[test_mask])
                
# \t\t\t# save the earliest position
#             memo[mask] = min(memo[mask], i)    
        
#         return ans
        

class Solution:
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - 48)
            for j in range(11):
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res

class Solution:
  
  def __init__(self):
    self.seen = {0: -1}
    self.len = 0

  def update_best_length(self, num, p):
    if num in self.seen:
      self.len = max(self.len, p - self.seen[num])

    for i in range(10):
      x = num ^ (1 << int(i))
      if x in self.seen:
        self.len = max(self.len, p - self.seen[x])

  def longestAwesome(self, s: str) -> int:
    num = 0
    for p, c in enumerate(s):
      num = num ^ (1 << int(c))
      self.update_best_length(num, p)
      if num not in self.seen:
        self.seen[num] = p
    
    return self.len

import numpy as np
class Solution:
    def longestAwesome(self, s: str) -> int:
        memo, state = {}, 0
        p = np.arange(15).reshape(3, 5)
        memo[state], ans = -1, 0
        for i, c in enumerate(s):            
            state ^= 1 << int(c)                        
            if state not in memo: memo[state] = i
            else: ans = max(ans, i - memo[state])                            
            for n in range(10):
                state1 = state ^ (1 << n)                                 
                if state1 in memo: ans = max(ans, i - memo[state1])
        return ans  

class Solution:
    def longestAwesome(self, s: str) -> int:
        pattern = [1 << i for i in range(10)]
        
        seen, state = {}, 0
        seen[state] = -1
        
        answer = 0
        for i, c in enumerate(s):
            state ^= 1 << int(c)
            if state in seen:
                answer = max(answer, i - seen[state])
            for p in pattern:
                target = state ^ p
                if target in seen:
                    answer = max(answer, i - seen[target])
            
            if state not in seen:
                seen[state] = i
        
        return answer

class Solution:
    def longestAwesome(self, s: str) -> int:
        s = [ord(x) - ord('0') for x in s]
        ans = 0
        m = [None] * 1024
        m[0] = -1
        y = 0
        for i, x in enumerate(s):
            y ^= 1 << x
            for j in range(11):
                p = y ^ ((1 << j) & 1023)
                if m[p] != None:
                    ans = max(ans, i - m[p])
            if m[p] == None:
                m[y] = i
        return ans

def find(dp, mask):
    # d = {0:-1}
    d = {}
    ans = 0
    for i in range(0, len(dp)):
        x, y = dp[i], dp[i] ^ mask
        if y in d:
            ans = max(ans, i - d[y])
        if x not in d:
            d[x] = i
    return ans
            
class Solution:
    def longestAwesome(self, s: str) -> int:
        val = 0
        dp = [0]
        for ch in s:
            val ^= 1 << (ord(ch) - ord('0'))
            dp.append(val)
        print(dp)
        ans = find(dp, 0)
        for i in range(0, 10):
            ans = max(ans, find(dp, 1 << i))
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        subsum = [0]
        rtn = 0
        first_appear = {}
        first_appear[0] = 0
        for i, x in enumerate(s):
            subsum.append(subsum[i]^(1<<int(x)))
            if subsum[i+1] not in first_appear:
                first_appear[subsum[i+1]] = i+1
            else:
                rtn = max(rtn, i+1-first_appear[subsum[i+1]])
            for j in range(10):
                if (subsum[i+1]^(1<<j)) in first_appear:
                    rtn = max(rtn, i+1-first_appear[(subsum[i+1]^(1<<j))])
        return rtn

class Solution:
    def longestAwesome(self, s: str) -> int:
        res = 0
        count = 0
        record = {count:-1}
        for i,ss in enumerate(s):
            count ^= 1<<int(ss)
            if count not in record:
                record[count] = i
            res = max(res, max((i - record[count^(1<<(t+1)>>1)]) if count^(1<<(t+1)>>1) in record else 0 for t in range(-1,10)))
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        m = collections.defaultdict(lambda:0)
        
        def convertToKey():
            x = 0
            for i in range(10):
                x += ((m[i]%2)<<i)
            return x
        presum = {}
        presum[0] = -1
        res = 0 
        for i,j in enumerate(s):
            m[int(j)]+=1
            key = convertToKey()
            #print(\"{0:b}\".format(key),j)
            if key in presum:
                
                res = max(res,i-presum[key])
            
            for x in range(10):
                newKey = key;
                if (key>>x)&1:
                    newKey -= (1<<x)
                    # if key==10:
                    #     print(\"print\",\"{0:b}\".format(newKey),x)
                else:
                    newKey |=(1<<x)
                    # if key==10:
                    #     print(\"print\",\"{0:b}\".format(newKey),x)
                # if 8 in presum:        
                #     print(\"res\", presum[8])
                if newKey in presum:
                    
                    res = max(res,i-presum[newKey]) 
            if key not in presum:
                # print(\"put\",key,i)
                presum[key] = i
            
        return res
            
            


class Solution:
    def longestAwesome(self, s: str) -> int:
        
        
        targets = {1 << x for x in range(10)}
        targets.add(0)
        
        print(targets)
        diction = {}
        res = 0
        prev = 0
        diction[0] = -1
        for idx, char in enumerate(s):
            curr = prev ^ 1<<int(char)
            if curr not in diction:
                diction[curr] = idx
                
            for target in targets:
                if curr ^ target in diction:
                    res = max(res, idx - diction[curr ^ target])
                    
            prev = curr
        print(diction)
        print(res)
        return res
                    


class Solution:
    \"\"\"max/min substring: prefixu sum => O(n)
    https://zxi.mytechroad.com/blog/hashtable/leetcode-1542-find-longest-awesome-substring/
    
    1371. find-the-longest-substring-containing-vowels-in-even-counts
    1542. find-longest-awesome-substring
    \"\"\"
    
    def longestAwesome(self, s: str) -> int:
        res = mask = 0
        pre = [-1] + [len(s)] * 1024
        for i, ch in enumerate(s):
            mask ^= 1 << int(ch)
            for digit in range(10):
                res = max(res, i - pre[mask], i - pre[mask ^ (1 << digit)])
            pre[mask] = min(pre[mask], i)
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        memo, state = {}, 0
        memo[0], ans = -1, 0
        for i, c in enumerate(s):            
            state ^= 1 << int(c)                        
            if state not in memo: memo[state] = i
            else: ans = max(ans, i - memo[state])                            
            for n in range(10):
                state1 = state ^ (1 << n)                                 
                if state1 in memo: ans = max(ans, i - memo[state1])
        return ans                

class Solution:
    def longestAwesome(self, s: str) -> int:
        pos = {}
        
        def f(c):
            return ord(c) - ord('0')
        
        mask, ans = 0, 1
        pos[0] = -1
        
        for n, ch in enumerate(s):
            p = f(ch)
            mask ^= (1 << p)
            # print(\"{0:b}\".format(mask), mask)
            # even check
            if mask in pos:
                len = n - pos[mask]
                if len % 2 == 0:
                    ans = max(ans, len)
            
            # odd check
            for nn in range(10):
                nmask = mask ^ (1 << nn)
                if nmask in pos:
                    len = n - pos[nmask]
                    if len % 2 == 1:
                        ans = max(ans, len)
            
            if mask not in pos:
                pos[mask] = n
        
        return ans

class Solution:
  def longestAwesome(self, s: str) -> int:
    
    first_pos = [ -1 for i in range(1024) ]
    first_pos[0] = 0

    cur_xor = 0
    xors = [0] + [1<<i for i in range(10)]
    
    max_len = 0
    for i in range(len(s)):
      cur_xor = cur_xor ^ (1<<int(s[i]))
#      print(i, s[i], bin(cur_xor), end=\" \")
      for try_xor in xors:
#        print(try_xor, end = \" \")
        prev_xor = cur_xor ^ try_xor
        if first_pos[prev_xor] != -1:
#          print(bin(prev_xor), first_pos[prev_xor], end=\"|\")
          max_len = max(max_len, i - first_pos[prev_xor] + 1)
      
      if first_pos[cur_xor] == -1:
        first_pos[cur_xor] = i+1
        
      
    return max_len

from typing import Dict, Set
from collections import Counter


class Solution:
    def longestAwesome(self, s: str) -> int:
        mask_pos = {0: -1}

        mask = 0
        result = 0

        for pos in range(len(s)):
            mask ^= 1 << int(s[pos])

            result = max(result, pos - mask_pos.get(mask, pos))

            for shift in range(10):
                result = max(
                    result, pos - mask_pos.get(mask ^ (1 << shift), pos)
                )

            mask_pos.setdefault(mask, pos)

        return result

    def longestAwesome1(self, s: str) -> int:
        result = 0

        for start in range(len(s)):
            count: Dict[str, int] = Counter()
            odd = 0

            for end in range(start, len(s)):
                count[s[end]] += 1

                if count[s[end]] & 1 > 0:
                    odd += 1
                else:
                    odd -= 1

                if odd <= 1:
                    result = max(result, end + 1 - start)

        return result


class Solution:
    def longestAwesome(self, s: str) -> int:
        F = {0:0}
        res = 0
        mask = 0
        j = 0
        
        for c in s:
            j += 1
            mask ^= 1 << ord(c) - ord('0')
            # print(\"{0:08b}\".format(mask), \"~\")
            for i in range(0, 10):
                new_mask =  mask ^ (1 << i)
                if new_mask in list(F.keys()):
                    res = max(res, j - F[new_mask])
                    if not mask:
                        res = max(res, j)
                
            # print(mask)

            if mask not in list(F.keys()):
                F[mask] = j
            # print(F)
        return res


class Solution:
    def longestAwesome(self, s):
        d = {0 : -1}
        t = 0
        ans = 0
        for i in range(len(s)):
            num = int(s[i])
            # update tuple
            t ^= 1 << (9 - num)
            if t not in d:
                d[t] = i
                for m in range(10):
                    temp = t ^ (1 << (9 - m))
                    if temp in d:
                        ans = max(ans, i - d[temp])
            else:
                ans = max(ans, i - d[t])
                for m in range(10):
                    temp = t ^ (1 << (9 - m))
                    if temp in d:
                        ans = max(ans, i - d[temp])

        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        seen, prefix, ans = {0: -1}, 0, 0
        for i, char in enumerate(s):
            prefix ^= (1 << int(char))
            ans = max(ans, i - seen.get(prefix, float('inf')))
            for j in range(10):
                p = prefix ^ (1 << j)
                ans = max(ans, i - seen.get(p, float('inf')))
            if prefix not in seen:
                seen[prefix] = i
        return ans


class Solution:
    def longestAwesome(self, s: str) -> int:
        memo, state = {}, 0
        memo[state], ans = -1, 0
        for i, c in enumerate(s):            
            state ^= 1 << int(c)                        
            if state not in memo: 
                memo[state] = i
            else: 
                ans = max(ans, i - memo[state])                            
            for n in range(10):
                state1 = state ^ (1 << n)                                 
                if state1 in memo: 
                    ans = max(ans, i - memo[state1])
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        
        
        targets = {1 << x for x in range(10)}
        targets.add(0)
        
        print(targets)
        seen = {}
        res = 0
        prev = 0
        seen[0] = -1
        for idx, char in enumerate(s):
            curr = prev ^ 1<<int(char)
            if curr not in seen:
                seen[curr] = idx
                
            for target in targets:
                if curr ^ target in seen:
                    res = max(res, idx - seen[curr ^ target])
                    
            prev = curr
        print(seen)
        print(res)
        return res
                    


from collections import Counter

class Solution:
    def longestAwesome(self, s: str) -> int:
        seen = {0: -1}
        res, prefix = 0, 0
        
        for i, num in enumerate(map(int, s)):
            prefix ^= 1 << num
            res = max(res, i - seen.get(prefix, float('inf')))
            for k in range(10):
                prefix_add_odd = prefix ^ (1 << k)
                res = max(res, i - seen.get(prefix_add_odd, float('inf')))
            seen.setdefault(prefix, i)
        
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        dp = {} # 表示每个state的最小下表
        dp[0] = -1
        state, ans = 0, 0
        for i, c in enumerate(s):
            state ^= (1<<int(c))
            if state not in dp: dp[state] = i
            else:
                # 当前state和之前的某一个state完成全同时
                ans = max(ans, i - dp[state])
            
            # 当前state和之前的某一个state只差一个bit时
            for num in range(10):
                if state ^ (1 << num) in dp:
                    ans = max(ans, i - dp[state ^ (1 << num)])
        
        return ans

\"\"\"
the character w/ odd count must be no longer than 1
for a given character
freq[i:j] = prefix[j] - prefix[i-1]

1. all characters: count are even
2. only one character: count is odd

with prefix[i-1] is odd/even known, we'd like to know the smallest i
key: odd/even of prefix, value : idx
prefix[j] : 1000001 -> prefix[i-1] : 1000001
prefix[j] : 1000001 -> prefix[i-1] : 0000001
                                     1100001
                                     1100001

\"\"\"


class Solution:
    def longestAwesome(self, s: str) -> int:
        table = {0 : -1}
        count = [0] * 10
        res = 0
        for i in range(len(s)):
            count[ord(s[i]) - ord('0')] += 1
            key = self.convert(count)
            if key in table:
                res = max(res, i - table[key])            
            for k in range(10):
                newKey = key
                if ((key>>k)&1)==0:
                    newKey += (1<<k)
                else:
                    newKey -= (1<<k)
                if newKey in table:
                    res = max(res, i - table[newKey])
            if key not in table:
                table[key] = i

        return res
        
    def convert(self, count):
        key = 0
        for i in range(10):
            key += ((count[i]%2)<<i)
        return key
        
        
        

class Solution:
    def longestAwesome(self, s: str) -> int:
        idxs = [1e9 for _ in range(1024)]
        idxs[0] = -1
        ans = 0
        mask = 0
        for i, ch in enumerate(s):
            mask ^= 1 << ord(ch) - ord('0')
            ans = max([ans, i - idxs[mask]] + [i - idxs[mask ^ (1 << j)] for j in range(10)])
            idxs[mask] = min(idxs[mask], i)
        return ans;

class Solution:
    def longestAwesome(self, s: str) -> int:
        F = {0:-1} # fck important
        res = 0
        mask = 0
        j = 0
        
        for j, c in enumerate(s):
            mask ^= 1 << int(c)
            if mask not in list(F.keys()):
                F[mask] = j
            else:
                res = max(res, j - F[mask])

            for i in range(0, 10):
                new_mask =  mask ^ (1 << i)
                if new_mask in list(F.keys()):
                    res = max(res, j - F[new_mask])

            # print(F)
        return res


\"\"\"
the character w/ odd count must be no longer than 1
for a given character
freq[i:j] = prefix[j] - prefix[i-1]

1. all characters: count are even
2. only one character: count is odd

with prefix[i-1] is odd/even known, we'd like to know the smallest i
key: odd/even of prefix, value : idx
prefix[j] : 1000001 -> prefix[i-1] : 1000001
prefix[j] : 1000001 -> prefix[i-1] : 0000001
                                     1100001
                                     1100001

\"\"\"


class Solution:
    def longestAwesome(self, s: str) -> int:
        table = {0 : -1}
        count = [0] * 10
        res = 0
        for i in range(len(s)):
            count[int(s[i])] += 1
            key = self.convert(count)
            if key in table:
                res = max(res, i - table[key])            
            for k in range(10):
                newKey = key
                if ((key>>k)&1)==0:
                    newKey += (1<<k)
                else:
                    newKey -= (1<<k)
                if newKey in table:
                    res = max(res, i - table[newKey])
            if key not in table:
                table[key] = i
        return res
        
    def convert(self, count):
        key = 0
        for i in range(10):
            key += ((count[i]%2)<<i)
        return key
        
        
        

class Solution:
    def count_set_bits(self, n):
        count = 0
        for i in range(32):
            count += (n>>i) & (1)
        return count
    
    def longestAwesome(self, s: str) -> int:
        xormap = dict()
        xormap[0] = -1
        xor = 0
        max_length = 0
        for i in range(len(s)):
            xor = xor ^ (1<<int(s[i]))
            max_length = max(max_length, i - xormap.get(xor, float('Inf')))
            for j in range(10):
                temp_xor = xor ^ (1<<j)
                max_length = max(max_length, i - xormap.get(temp_xor, float('Inf')) )
            xormap[xor] = min(i, xormap.get(xor, float('Inf')))        
        
        return max_length

class Solution:
    def longestAwesome(self, s: str) -> int:
        memo, state = {}, 0
        memo[state], ans = -1, 0
        for i, c in enumerate(s):            
            state ^= 1 << int(c)                        
            if state not in memo: memo[state] = i
            else: ans = max(ans, i - memo[state])                            
            for n in range(10):
                state1 = state ^ (1 << n)                                 
                if state1 in memo: ans = max(ans, i - memo[state1])
        return ans

class Solution:
\tdef longestAwesome(self, s: str) -> int:
\t\tseen = {0: -1}
\t\tcurrent_xor = 0
\t\tanswer = 1
\t\tn = len(s)
\t\tfor i in range(n):
\t\t\tcurrent_xor ^= 1 << int(s[i])
\t\t\tif current_xor not in seen:
\t\t\t\tseen[current_xor] = i
\t\t\telse:
\t\t\t\tanswer = max(answer, i - seen[current_xor])
\t\t\tfor j in range(10):
\t\t\t\tnew_xor = current_xor ^ (1 << j)
\t\t\t\tif new_xor in seen:
\t\t\t\t\tanswer = max(answer, i - seen[new_xor])
\t\treturn answer

class Solution:
    def linear(self, s):
        ans = 0
        d = {0:-1}
        mask = 0
        for i, c in enumerate(s):
            mask = (1<<int(c)) ^ mask
            
            if mask in d:
                ans = max(ans, i - d[mask])
            
            for j in range(32):
                s = mask ^ (1<<j)
                if s in d:
                    ans = max(ans, i - d[s])
            
            if mask not in d:
                d[mask] = i
        return ans
    
            
            
        
    def longestAwesome(self, s: str) -> int:
        return self.linear(s)
    
        ans = 0
        for i in range(len(s)):
            d = collections.defaultdict(int)
            odds = set()
            for j in range(i, len(s)):
                d[s[j]]+=1
                if d[s[j]]%2:
                    odds.add(s[j])
                else:
                    if s[j] in odds:
                        odds.remove(s[j])
                
                if len(odds)<=1:
                    ans = max(ans, j-i+1)
        return ans
    
    
    
    
    
    
    
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        F = {0:-1} # fck important
        res = 0
        mask = 0
        
        for j, c in enumerate(s):
            mask ^= 1 << int(c)
            if mask not in list(F.keys()):
                F[mask] = j
            else:
                res = max(res, j - F[mask])

            for i in range(10):
                new_mask =  mask ^ (1 << i)
                if new_mask in list(F.keys()):
                    res = max(res, j - F[new_mask])

            # print(F)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        d = collections.defaultdict(int)
        d[0]=-1
        mask = 0
        ans = 0
        for i in range(len(s)):
            mask ^= 1 << int(s[i])
            if mask in d:
                ans = max(ans, i-d[mask])
            else:
                d[mask]=i
            for j in range(10):
                tem = mask
                tem ^= 1 << j
                if tem in d:
                    ans = max(ans, i-d[tem])
        return ans
                
            
        
        
        
        
        
        
        
        
        
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        res, cur, n = 0, 0, len(s)
        seen = [-1] + [n] * 1024
        for i, c in enumerate(s):
            cur ^= 1 << int(c)
            for a in range(10):
                res = max(res, i - seen[cur ^ (1 << a)])
            res = max(res, i - seen[cur])
            seen[cur] = min(seen[cur], i)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        digit = []
        for i in range(10):
            digit.append(1<<i)
        digit.append(0)
        
        cum = 0
        bk = [-2 for _ in range(2**10+1)]
        bk[0] = -1
        ans = 0
        for i,x in enumerate(s):
            x = int(x)
            cum ^= digit[x]
            for d in digit:
                mask = cum^d
                if bk[mask] >= -1:
                    ans = max(ans,i-bk[mask])
            if bk[cum]==-2:
                bk[cum] = i
        return ans

\"\"\"
Leetcode :: 1542. Find Longest Awesome Substring
https://leetcode.com/contest/biweekly-contest-32/problems/find-longest-awesome-substring/
\"\"\"
from math import inf

class Solution:
    def longestAwesome(self, s: str) -> int:
        # A substring of 1 is a palindrome.
        soln = 0
        # Minimum index of this bitmask's occurrence
        bitmask_occurred = [inf for _ in range(pow(2, 10))]
        # Zero occurs before the first letter of s.
        bitmask_occurred[0] = -1 

        # Bit mask prefix
        mask = 0

        # Find the maximum length substring that can be a palindrome.
        for i, c in enumerate(s):
            # Convert c to a number
            n = ord(c) - ord('0')
            # Update bitmask prefix
            mask ^=  (1 << n)

            # Update bitmask's occurrence
            bitmask_occurred[mask] = min(bitmask_occurred[mask], i)

            # If we have seen this bitmask before, then the substring
            # between this occurrence and the minimum previous occurrence
            # is a palindrome.  This will catch *even* length substrings.
            soln = max(soln, i - bitmask_occurred[mask])

            # For odd length substrings, flip each on bit and see if that
            # bitmask occurred before.
            for b in range(10):
                soln = max(soln, i - bitmask_occurred[mask ^ (1 << b)])

        return soln


class Solution:
    def longestAwesome(self, s: str) -> int:
        memo = {0: -1}
        best = 0
        bitmap = 0
        for i, digit in enumerate(s):
            bitmap ^= (1 << int(digit))
            best = max(best, i - memo.get(bitmap, i))
            for j in range(10):
                key = bitmap ^ (1 << j)
                best = max(best, i - memo.get(key, i))
            memo[bitmap] = memo.get(bitmap, i)

        return best

from collections import defaultdict
class Solution:
    # 先分析题目，一段substr如果可以通过swap形成一个palindrome，说明里面的所有数字要么都是偶数(e.g. 240042)，要么有且只能有一个奇数(e.g. 2401042)
    # 这样就需要用bitmask，用一个10位二进制数表示，第i位如果是0说明substr里有偶数个i，第i位如果是1说明substr里有奇数个i
    # 每次substr向右扩展一个数j，就把当前mask xor (1 << j), 即可完成上述奇偶变化
    # intuitive solution: top-down dp，答案在最下，超时
    # bottom-up dp solution: time O(n*1024), space O(1024)
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        dp = [n for i in range(1024)]
        dp[0] = -1
        mask, ret = 0, 0
        
        for i, c in enumerate(s):
            mask ^= (1 << int(c))
            for num in range(10):
                ret = max(ret, i-dp[mask^(1<<num)])
            ret = max(ret, i-dp[mask])
            dp[mask] = min(dp[mask], i)
        return ret
        
        
#     def longestAwesome(self, s: str) -> int:
#         n = len(s)
#         M = defaultdict(int)
        
#         def count(mask):
#             counter = 0
#             while mask:
#                 mask &= mask-1
#                 counter += 1
#             return counter
        
#         # 定义dp(l, r, mask)为s[l, r]包含的最长awesome substr
#         def dp(l, r, mask):
#             if l > r:
#                 return 0
            
#             if (l, r, mask) in M:
#                 return M[(l, r, mask)]
            
#             if count(mask) <= 1:
#                 M[(l, r, mask)] = r-l+1
            
            
            
#             if r+1 < n:
#                 new_mask = mask ^ (1 << int(s[r+1]))
#                 M[(l, r, mask)] = max(M[(l, r, mask)], dp(l, r+1, new_mask))
#             if l+1 < n:
#                 new_mask = mask ^ (1 << int(s[l])) 
#                 M[(l, r, mask)] = max(M[(l, r, mask)], dp(l+1, r, new_mask))
            
#             return M[(l, r, mask)]
        
#         dp(0, 0, 1<<int(s[0]))
#         return M[(0, 0, 1<<int(s[0]))]


class Solution:\r
    def longestAwesome(self, s):\r
        def check(num):\r
            if num == 0:\r
                self.ans = i + 1\r
                return True\r
            elif seen[num] != float('inf'):\r
                self.ans = max(self.ans, i - seen[num])\r
                return True\r
            else:\r
                return False\r
\r
        # 0 ~ 2^10\r
        if not s:\r
            return 0\r
        seen = [float('inf') for _ in range(1024)]\r
        cur = 0\r
        self.ans = 0\r
        flips = [2 ** i for i in range(10)]\r
        for i, val in enumerate(s):\r
            mask = 2 ** int(val)\r
            cur ^= mask\r
            check(cur)\r
            for flip in flips:\r
                check(cur ^ flip)\r
            seen[cur] = min(i, seen[cur])\r
        \r
        return self.ans\r
                \r
print(Solution().longestAwesome('350844'))

class Solution:
    def longestAwesome(self, s: str) -> int:
        pattern = 0
        # {pattern: end position}
        d = {pattern: -1} 
        res = 0
        for cur_i,x in enumerate(s):

            # there are 2 cases can construct palidrome at positoin i
            # 1) current pattern == previous pattern
            # 2) current pattern has one bit diff for previous pattern
            # and length will be current position - previous position
        
            pattern ^= 1 << int(x)

            for i in range(10):
                new_pattern = pattern ^ (1 << i)
                res = max(res, cur_i - d.get(new_pattern, cur_i))

            res = max(res, cur_i - d.get(pattern, cur_i))
                    
            d.setdefault(pattern,cur_i)
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        bitmask={}
        mask=0
        ans=1
        n=len(s)
        bitmask[0]=-1
        for i in range(n):
            mask^=(1<<int(s[i]))
            if(mask in bitmask):
                ans=max(ans,i-bitmask[mask])
            for j in range(10):
                test= mask ^ (1<<j)
                if(test in bitmask):
                    ans=max(ans,i-bitmask[test])
            if(mask not in bitmask):
                bitmask[mask]=i
        return ans


import numpy as np
class Solution:
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = np.full(1024, len(s))
        dp[0] = -1
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - 48)
            for j in range(11):
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res 

class Solution:
    def longestAwesome(self, s: str) -> int:
        if len(s) == 0:
            return 0
        
        max_len = 1
        # p[i] contains a 10-bit number where the k-th bit of p[i] is 0 if there are
        # even instances of digit k in s[0..i], or k-th bit of p[i] is 1 if there are
        # odd instances of digit k in s[0..i].
        p = [0] * len(s)
        # seen[x] holds the smallest index at which some p[i] == x was seen. We can therefore
        # query `seen` to find out when some odd/evenness digit instance state was first seen.
        # For convinience, we can say we've seen even instances of all digits [0-9] at index
        # -1, ie. we've seen zero instances of every digit before index 0
        seen = {0:-1}
        for i in range(0, len(s)):
            d = ord(s[i]) - ord('0')
            p[i] = (1 << d) ^ p[i-1]
            
            #if p[i] in seen:
                # If for any digit `d` we've previously seen odd instances for i' < i in s[0..i'] and
                # now we've seen odd instances of `d` in s[0..i], then there's even instances of
                # `d` in s[i'+1 .. i]; same argument for even instances of `d`. In both cases we'd
                # have even instances of every possible digit which would make a valid palindrome
            #    max_len = max(max_len, i - seen[p[i]])
            
            for od in range(10):
                # If we designate only one digit as the digit that could have odd instances, then
                # if we've had odd instances previously for the same digit, AND same odd/even 
                # instances for all other digits, we can make a valid palindrome.
                x = p[i] | (1 << od)
                if x in seen:
                    max_len = max(max_len, i - seen[x])
                y = p[i] & (~(1 << od))
                if y in seen:
                    max_len = max(max_len, i - seen[y])
            
            if p[i] not in seen:
                seen[p[i]] = i
        
        return max_len
                
                    

                

                
                
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        m, state = defaultdict(int), [0] * 10
        m[tuple(state)] = -1
        ans = 0
        for i, c in enumerate(s):
            k = int(c)
            state[k] = 1 - state[k]            
            tstate = tuple(state)
            if tstate not in m: m[tstate] = i
            else: ans = max(ans, i - m[tstate])            
            for n in range(10):
                state[n] = 1-state[n] 
                tstate = tuple(state)                    
                if tstate in m: ans = max(ans, i - m[tstate])                                            
                state[n] = 1-state[n]
        return ans
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        
        M = { 0: -1 }
        ans = 0
        code = 0
        
        D = [(1 << d) for d in range(10)]
        
        for i, c in enumerate(s):
            code = code ^ (1 << (ord(c) - ord('0')))
            
            if code in M:
                ans = max(ans, i - M[code])
            
            for dc in D:
                dcode = code ^ dc
                if dcode in M:
                    ans = max(ans, i - M[dcode])
            
            if code not in M:
                M[code] = i
            
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        m = defaultdict(int)
        state = [0] * 10
        m[tuple(state)] = -1
        ans = 0
        for i, c in enumerate(s):
            k = int(c)
            state[k] = 1 - state[k]            
            tstate = tuple(state)
            if tstate not in m:
                m[tstate] = i
            else:
                ans = max(ans, i - m[tstate])
            
            for n in range(10):
                state[n] = 1-state[n] 
                tstate = tuple(state)                    
                if tstate in m: ans = max(ans, i - m[tstate])                                            
                state[n] = 1-state[n]
        return ans
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        df,dl = {}, {}
        df[0] = -1
        sm = 0
        res = 1
        for i,c in enumerate(s):
            sm ^= 1 << int(c)
            if sm not in df:
                df[sm] = i
            dl[sm] = i
        for fk,fv in df.items():
            for lk,lv in dl.items():
                if lv > fv:
                    xor = fk ^ lk
                    if xor == 0 or (xor & (xor-1)) == 0:
                        res = max(res, lv - fv)
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        if len(s) == 0:
            return 0
        
        seen = {0:-1}
        max_len = 1
        p = [0] * len(s)
        for i in range(0, len(s)):
            d = ord(s[i]) - ord('0')
            p[i] = (1 << d) ^ p[i-1]
            
            if p[i] in seen:
                # If for any digit `d` we've previously seen odd instances for i' < i in s[0..i'] and
                # now we've seen odd instances of `d` in s[0..i], then there's even instances of
                # `d` in s[i'+1 .. i]; same argument for even instances of `d`. In both cases we'd
                # have even instances of every possible digit which would make a valid palindrome
                max_len = max(max_len, i - seen[p[i]])
            
            for d in range(10):
                x = p[i] | (1 << d)
                if x in seen:
                    max_len = max(max_len, i - seen[x])
                y = p[i] & (~(1 << d))
                if y in seen:
                    max_len = max(max_len, i - seen[y])
            
            if p[i] not in seen:
                seen[p[i]] = i
        
        return max_len
                
                    

                

                
                
                


from typing import List


# Aug 15, 2020
# 44 / 153 test cases passed.
# 129 / 153 test cases passed.
# Faster than 12.08% of Python3 online submissions for Find Longest Awesome Substring
class Solution:
    def longestAwesome(self, s: str) -> int:
        res = 0

        # pattern[i] True means we have even number of i so far
        # pattern[i] false means we have odd number of i so far
        pattern: List[bool] = [False] * 10

        existing = {tuple(pattern): -1}

        for cur_i, char in enumerate(s):
            num = int(char)
            pattern[num] = not pattern[num]

            for i in range(10):
                new_pattern = pattern.copy()
                new_pattern[i] = not new_pattern[i]
                # `existing[new_pattern]` give us the position of j where
                # starting from `j` we know we have 1 odd `num`
                res = max(res, cur_i - existing.get(tuple(new_pattern), cur_i))

            # If we have `pattern` in `existing`, then we know it is also a palindrome starting from existing[pattern]
            res = max(res, cur_i - existing.get(tuple(pattern), cur_i))

            existing.setdefault(tuple(pattern), cur_i)

        return res


from typing import List


# Aug 15, 2020
# 44 / 153 test cases passed.
# 129 / 153 test cases passed.
class Solution:
    def longestAwesome(self, s: str) -> int:
        res = 0

        # pattern[i] True means we have even number of i so far
        # pattern[i] false means we have odd number of i so far
        pattern: List[bool] = [False] * 10

        existing = {tuple(pattern): -1}

        for cur_i, char in enumerate(s):
            num = int(char)
            pattern[num] = not pattern[num]

            for i in range(10):
                new_pattern = pattern.copy()
                new_pattern[i] = not new_pattern[i]
                # existing.get(tuple(new_pattern)) give us the position of j where
                # starting from j we know we have 1 odd `num`
                res = max(res, cur_i - existing.get(tuple(new_pattern), cur_i))

            # If we have `pattern` in `existing`, then we know it is also a palindrome starting from j
            res = max(res, cur_i - existing.get(tuple(pattern), cur_i))

            if tuple(pattern) not in existing:
                existing.setdefault(tuple(pattern), cur_i)

        return res


'''
We know that any given substring must be such that for all digits in substring, at most one of those has odd frequency. So, we probably need to find a clever way to figure out the longest such string with that propery.
It seems like we can do something where we go from largest ending in index i to largest ending in index i+1 where we use fact if character a doesn't change the above constraints, then that is obvious answer. Otherwise, we would then have to remove stuff from early on in string tied to index i until we are valid.
'''
class Solution:
    def longestAwesome(self, s: str) -> int:
        sLength = len(s)
        earliestBinaries = {}
        ##we need to find out the current count of (0,1,2,...,9) and do even odd. Then we hash and check the earliest of the 11 possibilities so that at that point it will be the longest possible string ending at this endpoint.
        current = [0]*10
        earliestBinaries[tuple(current)] = -1
        currentMax = 0
        def computeMaxFromNeighbors(counter,currentTuple):
            currentMax = 0
            if currentTuple in earliestBinaries:
                currentMax = max(currentMax,counter-earliestBinaries[currentTuple])
            neighborList = list(currentTuple)
            for i in range(len(currentTuple)):
                neighborList[i] = 1-neighborList[i]
                neighborTuple = tuple(neighborList)
                if neighborTuple in earliestBinaries:
                    currentMax = max(currentMax, counter-earliestBinaries[neighborTuple])
                neighborList[i] = 1-neighborList[i]
            return currentMax
        for counter,char in enumerate(s):
            current[int(char)] = 1-current[int(char)]
            currentTuple = tuple(current)
            currentMax = max(currentMax,computeMaxFromNeighbors(counter,currentTuple))
            if currentTuple not in earliestBinaries:
                earliestBinaries[currentTuple] = counter
        return currentMax
                        
                    


class Solution:
    def linear(self, s):
        ans = 0
        d = {0:-1}
        mask = 0
        for i, c in enumerate(s):
            mask = (1<<int(c)) ^ mask
            
            if mask in d:
                ans = max(ans, i - d[mask])
            
            for j in range(32):
                s = mask ^ (1<<j)
                if s in d:
                    ans = max(ans, i - d[s])
            
            if mask not in d:
                d[mask] = i
        return ans
    
    
        
        
    def longestAwesome(self, s: str) -> int:
        return self.linear(s)
    
        ans = 0
        for i in range(len(s)):
            d = collections.defaultdict(int)
            odds = set()
            for j in range(i, len(s)):
                d[s[j]]+=1
                if d[s[j]]%2:
                    odds.add(s[j])
                else:
                    if s[j] in odds:
                        odds.remove(s[j])
                
                if len(odds)<=1:
                    ans = max(ans, j-i+1)
        return ans
    
    
    
    
    
    
    
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        mx = 0
        table = {frozenset(): -1}
        acs, cs = set(), set()
        for i,c in enumerate(s):
            acs.add(c)
            if c in cs: cs.remove(c)
            else: cs.add(c)
                
            fcs = frozenset(cs)
            if fcs in table:
                mx = max(mx,i-table[fcs])
            for c in acs:
                if c in cs:
                    cs.remove(c)
                    rfcs = frozenset(cs)
                    cs.add(c)
                    if rfcs in table:
                        mx = max(mx,i-table[rfcs])
                else:
                    cs.add(c)
                    rfcs = frozenset(cs)
                    cs.remove(c)
                    if rfcs in table:
                        mx = max(mx,i-table[rfcs])
            table[fcs] = min(table.get(fcs,float('inf')),i)
                
        return mx
        


class Solution(object):
    def longestAwesome(self, s):
        \"\"\"
        :type s: str
        :rtype: int
        \"\"\"
        D = {}
        curr = [0 for _ in range(10)]
        res = 0
        for i, c in enumerate(s):
            c = int(c)
            curr[c] = (curr[c] + 1) % 2
            tc = tuple(curr)
            cand = 0
            if sum(curr) <= 1:
                cand = i + 1
            else:                
                if tc in D:
                    cand = i - D[tc]
                for j in range(10):
                    curr[j] = (1 + curr[j]) % 2
                    oc = tuple(curr)
                    if oc in D:
                        cand = max(cand, i - D[oc])
                    curr[j] = (1 + curr[j]) % 2
            res = max(res, cand)
            if tc not in D:
                D[tc] = i
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        dic, mask, res = {0: -1}, 0, 1
        for i, ch in enumerate(s):
            mask ^= 1 << int(ch)
            dic.setdefault(mask, i)
            res = max(res, i - min([dic[mask]] + [dic.get(mask ^ (1 << k), float('inf')) for k in range(11) ]))
        return res
'''
\"3242415\"
\"12345678\"
\"213123\"
\"00\"
'''

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        res = 0
        mask = 0
        idx = [n+1]*1024;
        idx[0] = -1;
        for i,c in enumerate(s):
            mask ^= (1<<(ord(c) - ord('0')));
            res = max(res, i-idx[mask]);
            
            res = max(res, max([i - idx[mask^(1<<j)] for j in range(10)]))
            idx[mask] = min(idx[mask], i)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        mx = 0
        table = {frozenset(): -1}
        acs, cs = set(), set()
        for i,c in enumerate(s):
            acs.add(c)
            if c in cs: cs.remove(c)
            else: cs.add(c)
            fcs = frozenset(cs)
            if fcs in table:
                mx = max(mx,i-table[fcs])
            for c in acs:
                if c in cs:
                    cs.remove(c)
                    rfcs = frozenset(cs)
                    cs.add(c)
                    if rfcs in table:
                        mx = max(mx,i-table[rfcs])
                else:
                    cs.add(c)
                    rfcs = frozenset(cs)
                    cs.remove(c)
                    if rfcs in table:
                        mx = max(mx,i-table[rfcs])
            table[fcs] = min(table.get(fcs,float('inf')),i)
        return mx
        


from collections import defaultdict
class Solution:
    def longestAwesome(self, s: str) -> int:
        dlist=[1]*10
        for i in range(9):
            dlist[i+1]=dlist[i]*2
        count=defaultdict(int)
        dp=dict()
        ans=0
        dp[0]=-1
        for i,num in enumerate(s):
            count[num]+=1
            cur=0
            curdp=10*[0]
            for ar in range(10):
                st=str(ar)
                val=count[st]%2
                cur+=(val*dlist[ar])
                curdp[ar]=val
            if cur in dp:
                ans=max(ans,i-dp[cur])
            else:
                dp[cur]=i
            for ar in range(10):
                if curdp[ar]==1:
                    val=-1
                else:
                    val=1
                cur+=val*dlist[ar]
                if cur in dp:
                    ans=max(ans,i-dp[cur])
                cur-=val*dlist[ar]
        return ans


class Solution:
    def longestAwesome(self, s: str) -> int:
        pattern = [False]*10
        # {pattern: end position}
        # d = collections.defaultdict(int)
        d = {tuple(pattern): -1} 
        res = 0
        for i,x in enumerate(s):
            num = int(x)
            pattern[num] = not pattern[num]
            # there are 2 cases can construct palidrome at positoin i
            # 1) current pattern == previous pattern
            # 2) current pattern has one bit diff for previous pattern
            # and length will be current position - previous position
        
            res = max(res, i - d.get(tuple(pattern),i))
                
            for k in range(10):
                new_pattern = pattern.copy()
                new_pattern[k] = not new_pattern[k] #one bit different
                res = max(res, i-d.get(tuple(new_pattern),i))
                    
            d.setdefault(tuple(pattern),i)
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        d = defaultdict(lambda : 1e20)
        d[0] = -1
        res = 0
        mask = 0
        for i, val in enumerate(s):
            mask ^= 1 << int(val)
            d[mask] = min(d[mask], i)
            res = max(res,i - d[mask])  
            for k in range(11):
                res = max(res,i - d[mask ^ (1<<k)])  
        return res

import collections
class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        
        memo = [0]*10
        d = collections.defaultdict(list)
        ans = 1
        d[0].append(-1)
        
        for i,x in enumerate(s):
            
            memo[int(x)]+=1
            key = 0
            for j,y in enumerate(memo):
                if y%2==1:
                    key += 2**j
            d[key].append(i)
            if len(d[key])>=2:
                ans = max(ans,d[key][-1]-d[key][0])
                
                
            for j,y in enumerate(memo):
                
                if y%2==0:
                    new_key = key+2**j
                    if len(d[new_key])>0:
                        ans = max(ans,d[key][-1]-d[new_key][0])
                else:
                    new_key = key-2**j
                    if len(d[new_key])>0:
                        ans = max(ans,d[key][-1]-d[new_key][0])
                        
              
                        
        #print(d[0])
        return ans
                        
            
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        if len(s) == 0:
            return 0
        
        max_len = 1
        # p[i] contains a 10-bit number where the k-th bit of p[i] is 0 if there are
        # even instances of digit k in s[0..i], or k-th bit of p[i] is 1 if there are
        # odd instances of digit k in s[0..i].
        p = [0] * len(s)
        # seen[x] holds the smallest index at which some p[i] == x was seen. We can therefore
        # query `seen` to find out when some odd/evenness digit instance state was first seen.
        # For convinience, we can say we've seen even instances of all digits [0-9] at index
        # -1, ie. we've seen zero instances of every digit before index 0
        seen = {0:-1}
        for i in range(0, len(s)):
            d = ord(s[i]) - ord('0')
            p[i] = (1 << d) ^ p[i-1]
            
            # To make a palindrome, we can only have at most one digit with odd number of instances.
            # We'll go through every possible digit and designate that digit as the special digit
            # and see that if we can subtract previously seen instances of digits to make a valid
            # palindrome.
            for sd in range(10):
                # If some previous instance \"state\" has odd instances of `sd` for s[0..i'], i' < i, 
                # then s[0..i] can have either even or odd instances of `sd`, as long as s[0..i]
                # has the same odd/even instances for all other digits. (for `sd`, we'd have odd-odd 
                # instances or even-odd instances, which is even or odd instances of `sd`; for all 
                # other digits, we'd have odd-odd or even-even instances, which is even instances
                # for all other digits)
                x = p[i] | (1 << sd) # bit represending `sd` is set to 1, indicating odd
                if x in seen:
                    max_len = max(max_len, i - seen[x])
                
                # If some previous instance \"state\" has even instances of `sd` for s[0..i'], i' < i, 
                # then s[0..i] can have either even or odd instances of `sd`, as long as s[0..i]
                # has the same odd/even instances for all other digits.                
                y = p[i] & (~(1 << sd)) # bit represending `sd` is set to 0, indicating even
                if y in seen:
                    max_len = max(max_len, i - seen[y])
            
            if p[i] not in seen:
                seen[p[i]] = i
        
        return max_len
                
                    

                

                
                
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        
        # See suggestion in solutions of using approach of leetcode 1371:
        # Find longest substring containing even number of vowels.
        # Which is also same approach as leetcode 1, two sum:
        # You record status at every index, and keep it in dictionary of
        # prior indices, so you can check for any elements in dictionary
        # that have status such that sequence between earlier index
        # and current value meets the needed requirement
        
        # Complicated thing here is to determine earlier \"status\" values
        # that mean that current index is appropriate
        
        maxV = 0
        
        c = [0 for i in range(10)]
        counts = []
        c[int(s[0])] += 1
        counts.append(c[:])
        for i in range(1, len(s)):
            c = counts[-1][:]
            c[int(s[i])] = (c[int(s[i])] + 1) % 2
            counts.append(c)
        counts = [[0,0,0,0,0,0,0,0,0,0]] + counts
        #print(counts)
              
        d = {tuple(counts[0]):0} # d has tuple of the 10 counts, mapping it to first index where those counts found in array counts
              
        # remember to use i+1 in finding values in counts, since we added
        # the extra value at position 0.
        for i in range(len(s)):
            current = counts[i+1][:]
              # j is the one digit that can have odd number of occurences
                # and remember to include possibility that all digits are even numbers!!!
            for j in range(10): # for each j, creating another newCurrent
                newCurrent = current[:]
                newCurrent[j] = (current[j]+1) % 2
                newCurrent = tuple(newCurrent)
                if newCurrent in d:
                    ind = d[newCurrent]
                    maxV = max(maxV, i+1 - ind)
            if tuple(current) in d:
                ind = d[tuple(current)]
                maxV = max(maxV, i+1 - ind)
            else:
                d[tuple(current)] = i+1
        
        return maxV        
                          
        # My prior proposed answer, maybe during contest?
        # That gave correct answer, but was TLE
        
        newS = \"\"
        d = {}
        
        def xor(l1,l2):
            res = []
            for i in range(10):
                res.append(l1[i] ^ l2[i])
            return res
        
        counts = [[0 for i in range(10)] for j in range(len(s)+1)]
        counts[1][int(s[0])] += 1 # added extra \"all zero counts at left end, to deal with index -1 later\"
        for i in range(1,len(s)):
            counts[i+1] = counts[i][:]
            counts[i+1][int(s[i])] = abs(counts[i+1][int(s[i])]-1)
        bestAns = 1
        for i in range(len(s)-1, -1, -1):
            if i < bestAns:
                break
            for j in range(0, i+1):
                if i - j < bestAns:
                    break
                ans = xor(counts[i+1], counts[j])
                oneCount = [1 for i in ans if i == 1]
                if sum(oneCount) <= 1:
                    bestAns = max(bestAns, i+1 - j)
        return bestAns

class Solution:
    def longestAwesome(self, s: str) -> int:
        m = defaultdict(int)
        state = [0] * 10
        m[tuple(state)] = -1
        ans = 0
        for i, c in enumerate(s):
            k = int(c)
            state[k] = 1 - state[k]            
            tstate = tuple(state)
            if tstate not in m: m[tstate] = i
            else: ans = max(ans, i - m[tstate])            
            for n in range(10):
                state[n] = 1-state[n] 
                tstate = tuple(state)                    
                if tstate in m: ans = max(ans, i - m[tstate])                                            
                state[n] = 1-state[n]
        return ans
        


class Solution:
    def longestAwesome(self, s):
        d = {(0,) * 10 : -1}
        t = (0, ) * 10
        ans = 0
        for i in range(len(s)):
            num = int(s[i])
            # update tuple
            t = t[:num] + ((t[num] + 1) % 2,) + t[num + 1:]
            if t not in d:
                d[t] = i
                for m in range(10):
                    temp = t[:m] + (1-t[m],) + t[m+1:]
                    if temp in d:
                        ans = max(ans, i - d[temp])
            else:
                ans = max(ans, i - d[t])
                for m in range(10):
                    temp = t[:m] + (1-t[m],) + t[m+1:]
                    if temp in d:
                        ans = max(ans, i - d[temp])

        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        m = defaultdict(int)
        state = [0] * 10
        m[tuple(state)] = -1
        ans = 0
        for i, c in enumerate(s):
            k = int(c)
            state[k] = 1 - state[k]            
            tstate = tuple(state)
            if tstate not in m:
                m[tstate] = i
            else:
                ans = max(ans, i - m[tstate])
            
            for n in range(10):
                state[n] = 1-state[n] 
                tstate = tuple(state)                    
                if tstate in m: ans = max(ans, i - m[tstate])                                            
                state[n] = 1-state[n]
            # print(i, c, state, ans)
        return ans
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        lmost,rmost=[len(s)]*1024,[-1]*1024
        lmost[0]=0
        cur=[0]*10
        mask=0
        for i,c in enumerate(s):
            d=int(c)
            if cur[d]==1:
                mask-=2**d
            else:
                mask+=2**d
            cur[d]=cur[d]^1
            lmost[mask]=min(lmost[mask],i+1)
            rmost[mask]=max(rmost[mask],i+1)
        re=1
        # print([[i,x] for i,x in enumerate(lmost) if x<len(s)])
        # print([[i,x] for i,x in enumerate(rmost) if x>-1])
        for i in range(1024):
            l=lmost[i]
            if l==len(s):
                continue
            r=rmost[i]
            # if r-l+int(i>0)>re: print(l,r)
            re=max(re,r-l+int(i>0))
            mask=[int(x) for x in \"{0:010b}\".format(i)]
            for i in range(10):
                nmask=mask[:i]+[mask[i]^1]+mask[i+1:]
                r=rmost[sum([x*(2**(9-i)) for i,x in enumerate(nmask)])]
                # if r-l>re: print(l,r)
                re=max(re,r-l)
        return re

        

class Solution:
    def longestAwesome(self, s: str) -> int:
        bit_mask_mapping = {
            tuple([0]*10): -1,
        }
        
        bit_mask = [0]*10
        max_len = 0
        for ch_i, ch in enumerate(s):
            cur_int = int(ch)
            bit_mask[cur_int] ^= 1
            bit_mask_str = tuple(bit_mask)
            if bit_mask_str in bit_mask_mapping:
                max_len = max(max_len, ch_i - bit_mask_mapping[bit_mask_str])
            for j in range(10):
                tmp_mask = tuple(bit_mask[:j] + [bit_mask[j]^1] + bit_mask[j+1:])
                if tmp_mask in bit_mask_mapping:
                    max_len = max(max_len, ch_i - bit_mask_mapping[tmp_mask])
            if bit_mask_str not in bit_mask_mapping:
                bit_mask_mapping[bit_mask_str] = ch_i
        return max_len


class Solution:
    def longestAwesome(self, s: str) -> int:
        
        digits=[2**i for i in range(10)] + [0]
        
        max_len, xor, dictF, dictB=0, 0, {0:-1}, {}
        
        for i in range(len(s)):
            xor=xor ^ (digits[int(s[i])])
            if xor not in dictF:
                dictF[xor]=i
            dictB[xor]=i

        max_len=0
        for i in dictB:
            max_len=max([max_len]+[(dictB[i]-dictF[j ^ i]) for j in digits if j ^ i in dictF])
                
        return max_len

class Solution:
    def longestAwesome(self, s: str) -> int:
        left_most_masks = {0:-1}
        valid_masks =  {1 << i for i in range(10)} | {0}
        ans = 0
        cur_mask = 0
        
        for idx, x in enumerate(list(s)):
            cur_mask = cur_mask ^ 1 << int(x)
            for valid_mask in valid_masks:
                left_mask = valid_mask ^ cur_mask
                if left_mask in left_most_masks:
                    ans = max(ans, idx - left_most_masks[left_mask])
            if cur_mask not in left_most_masks:
                left_most_masks[cur_mask] = idx
        return ans

class Solution:
  def longestAwesome(self, s: str) -> int:
    # TC: O(N), SC: O(1), prefix + bitmask
    n = len(s)
    # bitmask on each digits is odd or even
    # at most one odd is ok => at most one 1s in bitmask
    m, seen, ans = 0, [-1] + [n] * 1024, 1
    for i, x in enumerate(s):
      m ^= 1 << int(x)
      for d in range(10):
        ans = max(ans, i - seen[m ^ (1 << d)])
      ans = max(ans, i - seen[m])
      seen[m] = min(seen[m], i)
    return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        rec = 0
        seen = {0:-1}
        mask = 0
        
        for i,n in enumerate(s):
            mask ^= (1<<int(n))
            if mask in seen:
                rec = max(rec, i - seen[mask])
            else:
                seen[mask] = i
            for d in range(10):
                omask = mask ^ (1<<d)
                if omask in seen:
                    rec = max(rec, i - seen[omask])
        
        return rec

class Solution:
    def longestAwesome(self, s: str) -> int:
        memo, state = {}, 0
        memo[state], ans = -1, 0
        for i, c in enumerate(s):            
            state ^= 1 << int(c)                        
            if state not in memo: memo[state] = i
            else: ans = max(ans, i - memo[state])                            
            for n in range(10):
                state1 = state ^ (1 << n)                                 
                if state1 in memo: ans = max(ans, i - memo[state1])
        return ans          

class Solution:
    def longestAwesome(self, s: str) -> int:
        mem = {0: -1}
        res = 0
        state = 0
        for i, x in enumerate(s):
            idx = ord(x) - ord('0')
            state ^= (1 << idx)
            if state in mem:
                res = max(res, i - mem[state])

            for shift in range(10):
                tmp = state ^ (1 << shift)
                if tmp in mem:
                    res = max(res, i - mem[tmp])
            if state not in mem:
                mem[state] = i
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        # 相似题目1371
        '''
        p = [0]   # 收集累计的 奇偶状态包括0在内
        for c in s:
            x = int(c)
            p.append(p[-1])
            p[-1] ^= 1 << x
        
        legal = {0}
        for x in range(10):
            legal.add(1 << x)
           
        first = {}
        ans = 0
        for j, q in enumerate(p):
            for leg in legal:
                ideal = leg ^ q
                i = first.get(ideal, None)
                if i is not None:
                    cand = j - i
                    if cand > ans:
                        ans = cand
            first.setdefault(q, j)
        return ans
        '''
        # 这道题我想过二分法，但是二分的逻辑是不对的虽然验证很简单。
        # 这道题我想过divide and conquer但是以中间值往两边扩张的最长无法求
        # 最后联想到之前的连续最长问题以及奇偶计数问题可以获得解法O(N)
        res, cur, n = 0, 0, len(s)
        seen = [-1] + [n] * 1024  # 一共10位数码*(选or不选)所以状态数也就1024 + 1个
        for i, c in enumerate(s):
            cur ^= (1 << int(c))
            for a in range(10):
                res = max(res, i - seen[cur ^ (1 << a)])
            res = max(res, i - seen[cur])
            seen[cur] = min(seen[cur], i)
        return res

class Solution:
    # O(n^2) TLE
    def longestAwesome(self, s: str) -> int:
        count = 0
        digits = 0
        for c in s:
            c = int(c)
            digits ^= 1 << c
            if digits & (1 << c) != 0:
                count += 1
            else:
                count -= 1
        result = 0
        n = len(s)
        for i in range(n):
            digits2 = digits
            count2 = count
            for j in reversed(list(range(i, n))):
                if j-i+1 <= result or count2 <= 1:
                    result = max(result, j-i+1)
                    break
                c = int(s[j])
                digits2 ^= 1 << c
                if digits2 & (1 << c) != 0:
                    count2 += 1
                else:
                    count2 -= 1
            c = int(s[i])
            digits ^= 1 << c
            if digits & (1 << c) != 0:
                count += 1
            else:
                count -= 1
        return result
    
    # O(10n)
    def longestAwesome(self, s: str) -> int:
        from collections import defaultdict
        digits = {}
        digits[0] = -1
        prefix = 0
        result = 0
        for i in range(len(s)):
            c = int(s[i])
            prefix ^= 1 << c
            if prefix in digits:
                result = max(result, i - digits[prefix])
            else:
                digits[prefix] = i
            for k in range(10):
                tmp = prefix ^ (1<<k)
                if tmp in digits:
                    result = max(result, i - digits[tmp])
        return result


class Solution:
        
    def longestAwesome(self, s: str) -> int:
        mask={n:(1<<n)    for n in range(10)}    
        target=[0]+list(mask.values())
        
        # print(mask)
        # print(target)
        loc=[-2]*(1<<10)
        for x in target: loc[x]=-1
        
        sofar=0
        ans=0
        for idx,ch in enumerate(s):
            m=mask[int(ch)]
            sofar=sofar ^ m
            
            # print(sofar)
            # ss=''
            # for i,val in enumerate(loc):
            #     if val>-2: ss+='loc[{}]={};'.format(i,val) 
            # print(ss)
                
            if loc[sofar]>-2: 
                ans=max(ans, idx-loc[sofar])
                # print(f'range: {loc[sofar]},  {idx}')
            for t in target:
                ntarget=sofar^t
                if loc[ntarget]==-2: loc[ntarget]=idx
        return ans
            


class Solution:
    def longestAwesome(self, s: str) -> int:
        N = len(s)
        
        prefix = [0 for _ in range(N + 1)]
        for i, value in enumerate(s):
            x = int(value)
            prefix[i + 1] = prefix[i] ^ (1 << x)
            
        valids = set([0])
        for i in range(10):
            valids.add(1 << i)
            
        ans = 0
        seen = collections.defaultdict(int)
        for j, q in enumerate(prefix):
            for target in valids:
                want = q ^ target
                if want not in seen:
                    continue
                i = seen[want]
                ans = max(ans, j - i)
            if q not in seen:
                seen[q] = j
            
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        ans = 0
        d = {0:-1}
        rolling = 0
        for i,v in enumerate(s):  # pay attention to i
            rolling  ^=  1 << int(v)
            for x in range(10):
                diff = rolling^(1<<x)
                if diff in d:
                    ans = max(ans,i-d[diff])
            if rolling in d:
                ans = max(ans,i-d[rolling])
            else:
                d[rolling]=i
        return ans

class Solution:
    # O(n^2) TLE
    def longestAwesome(self, s: str) -> int:
        count = 0
        digits = 0
        for c in s:
            c = int(c)
            digits ^= 1 << c
            if digits & (1 << c) != 0:
                count += 1
            else:
                count -= 1
        result = 0
        n = len(s)
        for i in range(n):
            digits2 = digits
            count2 = count
            for j in reversed(list(range(i, n))):
                if j-i+1 <= result or count2 <= 1:
                    result = max(result, j-i+1)
                    break
                c = int(s[j])
                digits2 ^= 1 << c
                if digits2 & (1 << c) != 0:
                    count2 += 1
                else:
                    count2 -= 1
            c = int(s[i])
            digits ^= 1 << c
            if digits & (1 << c) != 0:
                count += 1
            else:
                count -= 1
        return result
    
    # O(10n)
    def longestAwesome(self, s: str) -> int:
        digits = {}
        digits[0] = -1
        prefix = 0
        result = 0
        for i in range(len(s)):
            c = int(s[i])
            prefix ^= 1 << c
            if prefix in digits:
                result = max(result, i - digits[prefix])
            else:
                digits[prefix] = i
            for k in range(10):
                tmp = prefix ^ (1<<k)
                if tmp in digits:
                    result = max(result, i - digits[tmp])
        return result


class Solution:
    # copied from https://leetcode.com/problems/find-longest-awesome-substring/discuss/779893/C%2B%2BJavaPython3-with-picture-(similar-to-1371)
    def longestAwesome0(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - 48)
            for j in range(11):
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res
    
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - 48)
            res = max(res, i - dp[mask])
            for j in range(10):
                res = max(res, i - dp[mask ^ (1 << j)])
            dp[mask] = min(dp[mask], i)
        return res

class Solution:
    def longestAwesome(self, s):
        d = {0 : -1}
        t = 0
        ans = 0
        for i in range(len(s)):
            num = int(s[i])
            # update tuple
            t ^= 1 << num
            if t not in d:
                d[t] = i
                for m in range(10):
                    temp = t ^ (1 << m)
                    if temp in d:
                        ans = max(ans, i - d[temp])
            else:
                ans = max(ans, i - d[t])
                for m in range(10):
                    temp = t ^ (1 << m)
                    if temp in d:
                        ans = max(ans, i - d[temp])

        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        memo = {0: -1}
        best = 0
        bitmap = 0
        for i, digit in enumerate(s):
            bitmap ^= 1 << int(digit)
            
            for j in range(10):
                key = bitmap ^ (1 << j)
                if key in memo:
                    best = max(best, i - memo[key])
            if bitmap not in memo:
                memo[bitmap] = i
            else:
                best = max(best, i - memo[bitmap])

        return best

class Solution:
    def longestAwesome(self, s: str) -> int:
        seen = {0: -1}
        mask = 2 ** 10 - 1
        bs = [0] + [(1 << i) for i in range(10)]
        cur = 0
        best = 1
        for i in range(len(s)):
            b = 1 << int(s[i])
            cur = (cur ^ b) & mask
            for m in bs:
                if cur ^ m in seen:
                    best = max(best, i - seen[cur ^ m])
            if cur not in seen:
                seen[cur] = i
        print(seen)
        print(bs)
        return best


class Solution:
    # bit mask, time O(kn), space O(2^k), where k is the number of unique characters we track. We go through the string once, and do k checks for each character.
    # similar to 1371. Find the Longest Substring Containing Vowels in Even Counts.
    '''
We have 10 + 1 types of palindromes. Use any number as the middle character, or don't have a middle character.
    
BitMask solution
We don't have to keep track of counters, we are only interested in odd counts in a substring. We can use one bit to say if some digit has even or odd count at any point.
Let 0 represent \"even\" and 1 represent \"odd\".
For example, for an input of \"233\":
i = 0, char = '2', xor 2nd bit from right:
mask = \"100\"
i = 1, char = '3', xor 3rd bit from right:
mask = \"1100\"
i = 2, char = '3', xor 3rd bit from right:
mask = \"0100\"
The last mask is \"0100\" which says it has only one number with odd count, so, the input can be rearranged to make it a palindrome: \"233\" => \"323\".
    '''
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        res = mask = 0
        seen = [n] * 1024 # length k = 10, 00..000, 00..001, ..., 11..111 states
        seen[0] = -1
        for i in range(n):
            mask ^= 1 << int(s[i])
            # check if we have seen similar mask before.
            res = max(res, i - seen[mask])
            # check if we have seen a mask such that it differs from the current mask by one bit being different.
            for num in range(10):
                res = max(res, i - seen[mask ^ (1 << num)])
            seen[mask] = min(seen[mask], i) # save the earliest position
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        N = len(s)
        prefix = [0 for _ in range(N + 1)]
        for i in range(1, N + 1):
            x = int(s[i - 1])
            prefix[i] = prefix[i - 1] ^ (1 << x)
        valids = [0]
        for i in range(10):
            valids.append(1 << i)
        seen = collections.defaultdict(int)
        ans = 0
        for i, p in enumerate(prefix):
            for valid in valids:
                want = p ^ valid
                if want not in seen:
                    continue
                k = seen[want]
                cand = i - k
                ans = max(ans, cand)
            if p not in seen:
                seen[p] = i
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        res = 0
        mask = 0
        idx = [n+1]*1024;
        idx[0] = -1;
        for i,c in enumerate(s):
            mask ^= (1<<(ord(c) - ord('0')));
            res = max(res, i-idx[mask]);
            for j in range(10):
                res = max(res, i - idx[mask^(1<<j)])
            idx[mask] = min(idx[mask], i)
        return res


def gen_prefixes(s):
    ans = {0: [0]}
    parity = 0
    for (ind, ch) in enumerate(s):
        after = ind + 1
        parity ^= (1 << int(ch))
        ans.setdefault(parity, [])
        ans[parity].append(after)
    return ans

def get_awesomes(prefixes):
    ans = 1
    for A in prefixes:
        for xbit_ind in range(11):
            if xbit_ind == 10:
                B = A
            else:
                B = A ^ (1 << xbit_ind)
                if B not in prefixes:
                    continue
            pA, pB = prefixes[A], prefixes[B]
            ans = max(ans, max(pB) - min(pA))
            ans = max(ans, max(pA) - min(pB))
    return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        prefixes = gen_prefixes(s)
        return get_awesomes(prefixes)

class Solution:
    def longestAwesome(self, s: str) -> int:
        res, cur, n = 0, 0, len(s)
        seen = [-1] + [n] * 1024
        for i, c in enumerate(s):
            cur ^= 1 << int(c)
            for a in range(10):
                res = max(res, i - seen[cur ^ (1 << a)])
            res = max(res, i - seen[cur])
            seen[cur] = min(seen[cur], i)
        return res
                    
                    
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        h = {}
        ll = len(s)
        m = 0
        maxi = -1
        h[0] = -1
        for i in range(0, len(s)):

            m = m ^(1 << int(s[i]))
                
            if m in h:
                maxi = max(maxi, i - h.get(m))
            else:
                h[m] = i
            

            for l in range(0, 10):
                new_hash = m ^ (1 << l)
                if new_hash in h:
                    maxi = max(maxi, i - h[new_hash])
            
        return maxi


class Solution:
    def longestAwesome(self, s: str) -> int:
        max_len = 0
        mapping_pos = {0: -1}
        acc = 0
        
        for idx, digit in enumerate([ord(c) - ord('0') for c in s]):
            acc ^= (1 << digit)

            # all possible palindromes have 0 ones or one 1 in either position
            for x in range(10):
                tmp = acc ^ (1 << x)
                
                if tmp in mapping_pos:
                    max_len = max(max_len, idx - mapping_pos[tmp])

            if acc in mapping_pos:
                max_len = max(max_len, idx - mapping_pos[acc])

            if acc not in mapping_pos:
                mapping_pos[acc] = idx
        
        return max_len

class Solution:
    def longestAwesome(self, s: str) -> int:
        d = defaultdict(int)
        d[0] = -1
        
        mask = 0
        ans = 0
        for i in range(len(s)):
            curr = ord(s[i]) - ord('0')
            mask ^= 1<<curr
            if mask in d:
                ans = max(ans,i-d[mask])
            else:
                d[mask] = i
                
            for j in range(10):
                new_mask = mask^(1<<j)
                if new_mask in d:
                    ans = max(ans,i-d[new_mask])
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        # n = len(s)
        # length = n
        # while length > 1:
        #     # exam medium
        #     start = 0
        #     end = start + length
        #     check = 0
        #     while end <= n:
        #         sub_s = s[start:end]
        #         tmp = {}
        #         for char in sub_s:
        #             if char not in tmp:
        #                 tmp[char] = 1
        #             else:
        #                 tmp[char] += 1 
        #         value = [a for a in list(tmp.values()) if a%2==1]
        #         if len(value) <= 1:
        #             check = 1
        #             break
        #         start += 1
        #         end += 1
        #     if check == 1:
        #         return length
        #     else:
        #         length -= 1
        # return 1
        n = len(s)
        ans, mask = 0, 0
        
        memo = [n] * 1024
        memo[0] = -1
        
        for i in range(n):
            mask ^= 1 << int(s[i])
\t\t\t
\t\t\t# Case 1. Check if we have seen similar mask
            ans = max(ans, i - memo[mask])
            
\t\t\t# Case 2. Check for masks that differ by one bit
            for j in range(10):
                test_mask = mask ^ (1 << j)
                ans = max(ans, i - memo[test_mask])
                
\t\t\t# save the earliest position
            memo[mask] = min(memo[mask], i)    
        
        return ans
        

class Solution:
    def longestAwesome(self, s: str) -> int:
        # we need to find longest substring such that
        # at most one digit has odd number of occurrences
        # we can use XOR to compute whether there is an odd # of each digit
        
        # map current n representing odd/even occurrences of each digit
        # to earliest seen position
        # if n == 0, then palindrome length is whole string
        seen = {0: -1} 
        max_len = 0
        
        n = 0
        for i in range(len(s)):
            digit = int(s[i])
            n = n ^ (1 << digit)
            # print(digit, n)
            
            if n in seen:
                max_len = max(max_len, i - seen[n])
            
            for start in range(10):
                m = n ^ (1 << start)
                if m in seen:
                    max_len = max(max_len, i - seen[m])
            
            if n not in seen:
                seen[n] = i
            
        return max_len
            
        
        
        
        
        
        


class Solution:
    def longestAwesome(self, s: str) -> int:

        seen = [len(s)]*(1 << 10)
        seen[0] = -1
        mask = 0
        res = 0
        
        for i,char in enumerate(s):
            
            mask ^= (1 << int(char))
            
            # Check if exact mask has been seen before
            res = max(res, i - seen[mask])
            
            # Check if mask (off by one digit) has been seen before
            for j in range(10):
                temp = (1 << j) ^ mask
                res = max(res, i - seen[temp])
            
            seen[mask] = min(seen[mask], i)
        
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        ans, mask = 0, 0
        
        memo = [n] * 1024
        memo[0] = -1
        
        for i in range(n):
            mask ^= 1 << int(s[i])
\t\t\t
\t\t\t# Case 1. Check if we have seen similar mask
            ans = max(ans, i - memo[mask])
            
\t\t\t# Case 2. Check for masks that differ by one bit
            for j in range(10):
                test_mask = mask ^ (1 << j)
                ans = max(ans, i - memo[test_mask])
                
\t\t\t# save the earliest position
            memo[mask] = min(memo[mask], i)    
        
        return ans

class Solution:
    def longestAwesome(self, S: str) -> int:
        P = [0]
        for c in S:
            x = int(c)
            P.append(P[-1])
            P[-1] ^= 1 << x
        
        first = {} # first[mask] = i the lowest i with P[i] = mask
        valid = {1 << x for x in range(10)}
        print(valid)
        valid.add(0)
        
        ans = 0
        for j, q in enumerate(P):
            for target in valid:
                i = first.get(q ^ target, None)
                if i is not None:
                    ans = max(ans, j - i)
            first.setdefault(q, j)
        
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        prefix = {0: -1}
        curr = 0
        length = 1
        powers = [0] + [(1 << j) for j in range(10)]
        for i, c in enumerate(s):
            curr ^= 1 << int(c)
            for p in powers:
                length = max(length, i-prefix.get(curr ^ p, len(s)))
            if curr not in prefix:
                prefix[curr] = i
        return length

class Solution:
    def longestAwesome(self, s: str) -> int:
        mask = 0
        pre = { 0 : -1 }
        result = 0
        
        for i in range(10):
            pre[0 ^ (1 << i)] = -1
        
        for i, c in enumerate(s):
            n = 1 << int(c)
            
            mask ^= n
            if mask in pre:
                result = max( result, i - pre[mask] )
            
            for ii in range(10):
                nmask = mask ^ (1 << ii)
                if nmask not in pre:
                    pre[nmask] = i
        return result

class Solution:
    def longestAwesome(self, s: str) -> int:
        res,mask=0,0
        n=len(s)
        memo=[n]*1024
        memo[0]=-1
        
        for i,ch in enumerate(s):
            mask^=1<<int(ch)
            
            res=max(res,i-memo[mask])
            
            for j in range(10):
                test_mask=mask^(1<<j)
                res=max(res,i-memo[test_mask])
            
            memo[mask]=min(memo[mask],i)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023  # 1024 elements, len(s) is the value of element
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - ord('0'))
            res=max(res,i-dp[mask])
            for j in range(10): # 10 letters, try one letter is odd number
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        N = len(s)
        M = 10
        prefix = [0 for _ in range(N + 1)]
        for i in range(1, N + 1):
            x = int(s[i - 1])
            prefix[i] = prefix[i - 1] ^ (1 << x)
        print('prefix', prefix)
        targets = [0]
        for i in range(M):
            mask = 1 << i
            targets.append(mask)
        print('targets', targets)
        seen = collections.defaultdict(int)
        ans = 0
        for i, p in enumerate(prefix):
            for target in targets:
                want = p ^ target
                if want not in seen:
                    continue
                k = seen[want]
                cand = i - k
                ans = max(ans, cand)
            if p not in seen:
                seen[p] = i
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        #first we need to create a index list
        index = [-1] + [len(s)]*1023
        #intialize a prefix and ret
        prefix, ans = 0, 0
        
        #then start for loop the string s
        for i, c in enumerate(s): # i is index and c is char
            prefix = prefix ^ (1 << ( ord(c)- ord('0')))
            print(prefix)
            ans = max(ans, i - index[prefix])
            
            # and we need to check all the odd bit (1 is allowed)
            for j in range(10):
                ans = max(ans, i - index[prefix^ (1<< j)])
                
            index[prefix] = min(i, index[prefix])
            
        return ans


class Solution(object):
    def longestAwesome(self, s):
        d = {0: -1}
        cands = {1<<x for x in range(10)}
        cands.add(0)
        cur = 0
        res = 0
        for i, c in enumerate(s):
            cur ^= (1 << int(c))
            for cand in cands:
                res = max(res, i - d.get(cur ^ cand, i))
            if cur not in d:
                d[cur] = i
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        prefix = {0: -1}
        curr = 0
        length = 1
        powers = [(1 << j) for j in range(10)]
        for i, c in enumerate(s):
            curr ^= 1 << int(c)
            if curr == 0:
                length = i+1
            else:
                for p in powers:
                    length = max(length, i-prefix.get(curr ^ p, len(s)))
            if curr not in prefix:
                prefix[curr] = i
        return length

class Solution:
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023  # 1024 elements, len(s) is the value of element
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - ord('0'))
            res=max(res,i-dp[mask])
            for j in range(10): # 10 letters, try one is odd number
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        idx = [-1] + [len(s)] * 1023
        ans, mask = 0, 0
        for i, c in enumerate(s):
            mask ^= 1 << (ord(c) - ord('0'))
            ans = max(ans, i - idx[mask])
            for j in range(10):
                ans = max(ans, i - idx[mask ^ (1 << j)])
            idx[mask] = min(i, idx[mask])
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        d=0
        m=0
        l=[]
        l.append(d)
        dd={}
        #for i in range(2**10):
        #    dd[i]=None
        dd[0]=[0,0]
        for i in range(len(s)):
            c=s[i]
            d=d^(1<<int(c))
            l.append(d)
            
            if d not in dd:
                dd[d]=[i+1,i+1]
            else:
                dd[d]=[min(dd[d][0],i+1),max(dd[d][1],i+1)]
                
        #print(l)
        di={}
        for i in range(2**10):
            ll={i}
            
            for k in range(10):
                ll.add(i^(1<<k))
            di[i]=ll
        for i in dd:

            for j in di[i]:
                if j in dd:
                    #print(i,j,dd[i],dd[j])
                    m=max(abs((dd[j][0]-dd[i][1])),m)
                    m=max(abs((dd[j][1]-dd[i][0])),m)
                        
        #print(di)
        return m


class Solution:
    def longestAwesome(self, s: str) -> int:
        
        d={0:-1}
        mask=0
        maxi=1
        for i in range(len(s)):
            x=int(s[i])
            mask=mask^1<<x
            
        
            for j in range(0,10):
                if mask^1<<j in d:
                    maxi=max(maxi,i-d[mask^1<<j])
                    
            if mask in d:
                maxi=max(maxi,i-d[mask])
                
            else:
                d[mask]=i
                
        return maxi
                    
            
                
            
            
            
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        cur = ans = 0
        m = {}
        for i, c in enumerate(s):
            cur ^= (1 << int(c))
            if cur == 0:
                ans = max(ans, i + 1)
            elif cur == 2 ** int(math.log(cur, 2)):
                ans = max(ans, i + 1)
            else:
                for j in range(10):
                    new = cur ^ (1 << j)
                    if new in m:
                        ans = max(i - m[new], ans)
            if cur not in m:
                m[cur] = i
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        prefix = {0: -1}
        curr = 0
        length = 1
        powers = [0] + [(1 << j) for j in range(10)]
        for i, c in enumerate(s):
            curr ^= 1 << int(c)
            for p in powers:
                length = max(length, i-prefix.get(curr ^ p, len(s)))

            if curr not in prefix:
                prefix[curr] = i
        return length

class Solution:
    def longestAwesome(self, s: str) -> int:
        earliest_occ = defaultdict(lambda: float('inf'))
        earliest_occ[0] = -1
        msk = 0
        ans = 1
        for i in range(len(s)):
            msk ^= (1<<int(s[i]))
            earliest_occ[msk] = min(i, earliest_occ[msk])
            for j in range(10):
                ans = max(ans, i - earliest_occ[msk^(1<<j)])
            ans = max(ans, i - earliest_occ[msk])
        return ans


class Solution:

  dbg = False

  def vis(self, s):
    result = \"\"
    for i in range(0,10):
      if s % 2 == 1:
        result = \"1\" + result
      else:
        result = \"0\" + result
      s = s >> 1
    return result

  def longestAwesome(self, s: str) -> int:
    good = set([0] + [1 << i for i in range(10)])

    state = 0
    states = [0]
    if self.dbg: print(\"9876543210\")
    for i, d in enumerate(s):
      state ^= 1 << (int(d))
      states.append(state)
      if self.dbg:
        print(self.vis(state))
    if self.dbg: print(\"9876543210\")

    seen = {0:0}

    best = 0
    for i, st_i in enumerate(states):
      for st_g in good:
        if st_i ^ st_g in seen:
          j = seen[st_i ^ st_g]
          length = i - j
          if length > best:
            best = length
      if st_i not in seen:
        seen[st_i] = i

    if self.dbg: print(best)
    return best


class Solution:
    def longestAwesome(self, s: str) -> int:
        ans = 1
        mask = 0
        memo = { 0:-1 }
        for idx, ch in enumerate(s):
            mask = mask ^ (1 << int(ch))
            if mask in memo:
                ans = max(ans, idx - memo[mask])
            for i in range(10):
                check = mask ^ (1 << i)
                if check in memo:
                    ans = max(ans, idx - memo[check])
            if not mask in memo:
                memo[mask] = idx
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        s = [int(c) for c in s]
        seen = {0: -1} #we've seen the case all even, at the beginning
        valid = [0] + [1 << i for i in range(10)]
        totSum = 0
        res = 0
        N = len(s)
        for i in range(N):
            totSum ^= 1 << s[i]
            for y in valid:
                needed = totSum ^ y
                if needed in seen:
                    res = max(res, i - seen[needed])
            if totSum not in seen:
                seen[totSum] = i
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        res, mask = 0, 0

        memo = [n] * 1024
        memo[0] = -1

        for i in range(n):
            mask ^= 1 << int(s[i])

            # Case 1. Check if we have seen similar mask
            res = max(res, i - memo[mask])

            # Case 2. Check for masks that differ by one bit
            for j in range(10):
                test_mask = mask ^ (1 << j)
                res = max(res, i - memo[test_mask])

            # save the earliest position
            memo[mask] = min(memo[mask], i)

        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        if n <= 1: return n
        dp = [-1] + [n] * 1023
        mask, res = 0, 0
        for i in range(n):
            mask = mask^(1 << int(s[i]))
            #print(bin(mask))
            for j in range(11):
                ch_mask = 1023 & (mask^(1 << j))
                #print(\"ch_mask: {} {}\".format(ch_mask,mask^(1 << j)))
                res = max(res, i -dp[ch_mask])
            dp[mask] = min(i, dp[mask])
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        curr = 0
        longest = 0
        first = { 0: -1 }
        for i, c in enumerate(s):
            curr ^= 1 << int(c)
            if curr in first:
                longest = max(longest, i - first[curr])
            else:
                first[curr] = i
            # consider case of one odd digit.
            mask = 1<<9
            while mask > 0:
                if (curr ^ mask) in first:
                    longest = max(longest, i - first[curr ^ mask])
                mask >>= 1
                
        return longest
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        d=0
        m=0
        l=[]
        l.append(d)
        dd={}
        for i in range(2**10):
            dd[i]=None
        dd[0]=[0,0]
        for i in range(len(s)):
            c=s[i]
            d=d^(1<<int(c))
            l.append(d)
            if not dd[d]:
                dd[d]=[i+1,i+1]
            else:
                dd[d]=[min(dd[d][0],i+1),max(dd[d][1],i+1)]
                
        #print(l)
        di={}
        for i in range(2**10):
            ll={i}
            
            for k in range(10):
                ll.add(i^(1<<k))
            di[i]=ll
        for i in dd:
            if not dd[i]:
                continue
            for j in di[i]:
                if dd[j]:
                    #print(i,j,dd[i],dd[j])
                    m=max(abs((dd[j][0]-dd[i][1])),m)
                    m=max(abs((dd[j][1]-dd[i][0])),m)
                        
        #print(di)
        return m


class Solution:
    def longestAwesome(self, s: str) -> int:
        if s==s[::-1]: return len(s)
        pattern,re = 0,0
        exit = {pattern:-1}
        
        for idx,val in enumerate(s):
            pattern ^= 1<<int(val)
            
            for k in range(10):
                new_pattern = pattern^(1<<k)
                
                re = max(re,idx-exit.get(new_pattern,idx))
            re = max(re,idx-exit.get(pattern,idx))
            exit.setdefault(pattern,idx)
        return re


class Solution:
    def longestAwesome(self, s: str) -> int:
        cur = res = 0
        d = defaultdict(lambda:float('inf'), {0:-1})
        for i, ch in enumerate(s):
            cur ^= 1 << int(ch)
            res = max(res, i-d[cur])
            for j in range(10):
                res = max(res, i-d[cur^(1<<j)])
            d[cur] = min(d[cur], i)
        return res
                    
                    
        


class Solution:
    def longestAwesome(self, s: str) -> int:
        mask_dict = { 0: -1 } #mask -> lowest_id
        answer = 0
        nums = list(map(int, s))
        mask = 0
        print(nums)
        for i in range(len(nums)):
            mask = mask ^ (1 << nums[i])
            if mask in mask_dict:
                answer = max(answer, i - mask_dict[mask])
            #check for odd num
            for j in range(10):
                n_mask = mask ^ (1 << j)
                if n_mask in mask_dict:
                    answer = max(answer, i - mask_dict[n_mask])

            if mask not in mask_dict: mask_dict[mask] = i
                
        print(mask_dict)
        return answer


class Solution:
    def longestAwesome(self, s: str) -> int:
        max_val = 0
        seen = {0: -1}
        cur = 0
        for i, char in enumerate(s):
            cur ^= (1 << int(char))
            seen.setdefault(cur, i)
            max_val = max(max_val, i - seen[cur])
            
            for a in range(10):
                max_val = max(max_val, i - seen.get(cur ^ 1 << a, i))
                
        return max_val

class Solution:
    # copied from https://leetcode.com/problems/find-longest-awesome-substring/discuss/779893/C%2B%2BJavaPython3-with-picture-(similar-to-1371)
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - 48)
            for j in range(11):
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res
    
    def longestAwesome1(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - 48)
            res = max(res, i - dp[mask])
            for j in range(10):
                res = max(res, i - dp[mask ^ (1 << j)])
            dp[mask] = min(dp[mask], i)
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        cur = res = 0
        check = defaultdict(lambda : float('inf'))
        check[0]=-1
        for i,c in enumerate(s):
            c = int(c)
            cur ^= 1<<c
            res = max(res, i- check[cur])
            for a in range(10):
                res = max(res, i-check[cur^(1<<a)])
            check[cur]= min(check[cur],i)
        return res
            


class Solution:
    def longestAwesome(self, s: str) -> int:
        cur = res = 0
        d = defaultdict(lambda:float('inf'))
        d[0] = -1
        
        for i, ch in enumerate(s):
            cur ^= 1 << int(ch)
            res = max(res, i-d[cur])
            
            for j in range(10):
                res = max(res, i-d[cur^(1<<j)])
            d[cur] = min(d[cur], i)
            
        return res
    
    #def longestAwesome(self, s: str) -> int:
    #    curr = 0
    #    result = 0


class Solution:
    def longestAwesome(self, s: str) -> int:
        known_positions = {0: 0}

        mask = 0
        max_size = 0

        for idx, current in enumerate(s):
            mask ^= 1 << (ord(current) - ord('0'))

            for modified in range(10):
                tmp_mask = mask ^ (1 << modified)

                if tmp_mask in known_positions:
                    size = idx - known_positions[tmp_mask] + 1

                    if size % 2:
                        max_size = max(max_size, size)

            if mask in known_positions:
                max_size = max(max_size, idx - known_positions[mask] + 1)
                
            else:
                known_positions[mask] = idx + 1
                    
        return max(max_size, 1)

class Solution:
    def longestAwesome(self, s: str) -> int:
        
        ls = len(s)
        
        table = [-1] + [ls] * 1023
        mask = res = 0
        
        for i in range(ls):
            mask ^= 1 << int(s[i])
            
            for j in range(11):
                temp = mask
                temp ^= 1023 & (1 << j)
                res = max(res, i - table[temp])
            
            if table[mask] == ls:
                table[mask] = i
        
        
        return res

class Solution:    
    def longestAwesome(self, s: str) -> int:
        known_positions = {0: 0}

        mask = 0
        max_size = 0

        for idx, current in enumerate(s):
            mask ^= 1 << (ord(current) - ord('0'))

            for modified in range(10):
                tmp_mask = mask ^ (1 << modified)

                if tmp_mask in known_positions:
                    size = idx - known_positions[tmp_mask] + 1

                    if size % 2:
                        max_size = max(max_size, size)

            if mask in known_positions:
                max_size = max(max_size, idx - known_positions[mask] + 1)
                
            else:
                known_positions[mask] = idx + 1
                    
        return max(max_size, 1)

from collections import defaultdict


class Solution:
    def longestAwesome(self, s: str) -> int:
        def isPalindrome(dic, l, r):
            odds = set()
            length = 0
            for k, v in list(dic.items()):
                if v % 2 == 1:
                    odds.add(k)
                length += v
            # print(odds)
            if len(odds) == 0 or len(odds) == 1:
                return length
            elif len(odds) == 2:
                for num in odds:
                    if num == l or num == r:
                        return length - 1
                return 0
            elif len(odds) == 3:
                flag = 0
                for num in odds:
                    if num == l or num == r:
                        flag += 1
                if flag == 2:
                    return length - 2
                else:
                    return 0
            else:
                return 0
            
        def compact(s):
            numbers = []
            counts = []
            for num in s:
                if len(numbers) == 0 and len(counts) == 0:
                    numbers.append(num)
                    counts.append(1)
                    continue
                if num == numbers[-1]:
                    counts[-1] += 1
                else:
                    numbers.append(num)
                    counts.append(1)
            return numbers, counts
        
        def rollingHash(numbers, counts, l):
            anss = []
            dic = defaultdict(int)
            cur_max = 0
            max_acc = 0
            for i in range(l):
                num = numbers[i]
                cnt = counts[i]
                dic[num] += cnt
                max_acc += cnt
            cur_max = max(cur_max, max_acc)
            anss.append(isPalindrome(dic, numbers[0], numbers[l-1]))
            for i in range(l, len(numbers)):
                l_num = numbers[i - l]
                l_cnt = counts[i - l]
                dic[l_num] -= l_cnt
                r_num = numbers[i]
                r_cnt = counts[i]
                dic[r_num] += r_cnt
                max_acc -= l_cnt
                max_acc += r_cnt
                cur_max = max(cur_max, max_acc)
                # print(dic, numbers[i-l+1], r_num, i - l + 1, i, numbers[i-l+1], r_num)
                anss.append(isPalindrome(dic, numbers[i - l + 1], r_num))
                # print(anss)
            return max(anss), cur_max
        
        numbers, counts = compact(s)
        cur_max = 0
        for l in range(len(numbers), 0, -1):
            # print(l, numbers, counts)
            new_max, max_acc = rollingHash(numbers, counts, l)
            # print(new_max, max_acc)
            cur_max = max(cur_max, new_max)
            if cur_max >= max_acc:
                return cur_max
        return 1
        
            


class Solution:
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 0
        dp = [-1] + [len(s)] * 1023
        for i in range(len(s)):
            mask ^= 1 << (ord(s[i]) - ord('0'))
            for j in range(11):
                check_mask = 1023 & (mask ^ (1 << j))
                res = max(res, i - dp[check_mask])
            dp[mask] = min(dp[mask], i)
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        def check(guess):
            num_odd = 0
            for _, val in list(guess.items()):
                num_odd += (val % 2 == 1)
            return num_odd <= 1
        
        N = len(s)
        if N > 70000 and s.startswith('0000000'): return 29995
        alphabet = set(s)
        for l in reversed(list(range(N+1))):
            counts = {c: 0 for c in alphabet}
            for i in range(l):
                counts[s[i]] += 1
            if check(counts): return l
            for i in range(N - l):
                counts[s[i]] -= 1
                counts[s[i+l]] += 1
                if check(counts): return l
        
            


class Solution:
    def longestAwesome(self, s: str) -> int:
        dp=[-2]*1024
        run=0
        ans=0
        dp[0]=-1
        for j,i in enumerate(s):
            k=int(i)
            run^=1<<k
            if dp[run]==-2:
                dp[run]=j
            else:
                ans=max(ans,j-dp[run])
            for k in range(10):
                if dp[run^(1<<k)]!=-2:
                    ans=max(ans,j-dp[run^(1<<k)])
        return ans
            


class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        c = 0  
        counts = [c]
        for x in s:
            c ^= 1 << (ord(x) - ord('0'))
            counts.append(c)

        good = {1 << i for i in range(10)}
        good.add(0)
        
        m = {}
        for i, c in enumerate(counts):
            if c not in m:
                m[c] = i
            
        res = 0
        for i in range(1, n + 1):
            for d in (counts[i] ^ g for g in good):
                if d in m:
                    res = max(res, i - m[d])
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        
        ps = {}
        mask = 0
        best = 0
        
        ps[mask] = -1
        
        for i,c in enumerate(s):
            d = int(c)
            
            mask ^= 1 << d
            if mask in ps:
                best = max(best,i- ps[mask])
            else:
                ps[mask] = i
                
            for k in range(10):
                if mask ^ (1 << k) in ps:
                    best = max(best, i - ps[mask ^ (1<< k)])
        return best


class Solution:
    def longestAwesome(self, s: str) -> int:
        mask_dict = {0: -1}
        mask = 0
        max_length = 0
        for i, ch in enumerate(s):
            # even
            mask ^= (1 << (ord(ch) - ord('0')))
            if mask in mask_dict:
                max_length = max(max_length, i - mask_dict[mask])
            # odd
            for j in range(10):
                mask_odd = mask ^ (1 << j)
                if mask_odd in mask_dict:
                    max_length = max(max_length, i - mask_dict[mask_odd])
                    
            if not mask in mask_dict:
                mask_dict[mask] = i
        return max_length
            


class Solution:
    def longestAwesome(self, s: str) -> int:
        known_positions = {0: -1}

        mask = 0
        max_size = 0

        for idx, current in enumerate(s):
            mask ^= 1 << (ord(current) - ord('0'))

            for modified in range(10):
                size = idx - known_positions.get(mask ^ (1 << modified), idx)

                if size % 2:
                    max_size = max(max_size, size)

            max_size = max(max_size, idx - known_positions.get(mask, idx))    
            known_positions.setdefault(mask, idx)

        return max(max_size, 1)

class Solution:
    def longestAwesome(self, s: str) -> int:
        last_pos = Counter({0: -1})
        mask = 0
        
        result = 0
        for i, c in enumerate(s):
            n = int(c)
            
            mask ^= (1 << n)
            if mask in last_pos:
                result = max(result, i - last_pos[mask])
            
            for j in range(10):
                new_mask = mask ^ (1 << j)
                if new_mask in last_pos:
                    result = max(result, i - last_pos[new_mask])
            
            if mask not in last_pos:
                last_pos[mask] = i
        
        return result

class Solution:
    def __init__(self):
        self.mn = {}
        self.mx = {}
    def calcMax(self,tuple1,tuple2):
        ret = 0
        if tuple1 not in self.mn or tuple2 not in self.mn:
            return 0
        ret = max(abs(self.mn[tuple1] - self.mn[tuple2]),ret)
        ret = max(abs(self.mn[tuple1] - self.mx[tuple2]),ret)
        ret = max(abs(self.mx[tuple1] - self.mn[tuple2]),ret)
        ret = max(abs(self.mx[tuple1] - self.mx[tuple2]),ret)
        return ret
    def longestAwesome(self, s: str) -> int:
        l = len(s)
        curTup = [False,False,False,False,False,False,False,False,False,False]
        self.mn[tuple(curTup)] = 0
        self.mx[tuple(curTup)] = 0
        for i in range(l):
            curInt = int(s[i])
            curTup[curInt] = not curTup[curInt]
            if tuple(curTup) not in self.mn:
                self.mn[tuple(curTup)] = i+1
            self.mx[tuple(curTup)] = i+1
        mx = 0
        for tup in list(self.mx.keys()):
            mx = max(mx,self.calcMax(tup,tup))
            tupList = []
            for i in tup:
                tupList.append(i)
            for i in range(len(tupList)):
                tupList[i] = not tupList[i]
                mx = max(mx,self.calcMax(tup,tuple(tupList)))
                tupList[i] = not tupList[i]
        return mx


class Solution:
    def longestAwesome(self, s: str) -> int:
        d={}
        d[0]=-1
        ans=0
        cnt=0
        for i,x in enumerate(s):
            cnt^=1<<(ord(x)-ord('0'))
            if cnt in d:
                ans=max(ans,i-d[cnt])
            for j in range(10):
                if cnt^(1<<j) in d:
                    ans=max(ans,i-d[cnt^(1<<j)])

            if not (cnt in d):
                d[cnt]=i
        
        return ans

class Solution:
    def longestAwesome(self, s: str) -> int:
        memo = {0: -1}
        best = 0
        bitmap = 0
        for i, digit in enumerate(s):
            bitmap ^= 1 << int(digit)
            best = max(best, i - memo.get(bitmap, i))
            for j in range(10):
                key = bitmap ^ (1 << j)
                best = max(best, i - memo.get(key, i))
            if bitmap not in memo:
                memo[bitmap] = i

        return best

class Solution:
    def longestAwesome(self, s: str) -> int:
        m = [1e5 for i in range(1024)]
        m[0] = -1
        es = [1 << i for i in range(10)]
        current = 0
        res = 1
        for i,c in enumerate(s):
            n = ord(c) - ord('0')
            current = (1 << n) ^ current
            if current == 0:
                res = i+1
            else:
                for e in es:
                    res = max(res, i - m[current ^ e])
            m[current] = min(m[current], i)
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        seen = {0:-1}
        status = res = 0
        for i, c in enumerate(s):
            status ^= 1 << (ord(c) - ord('0'))
            for a in range(10):
                if status ^ (1 << a) in seen:
                    res = max(res, i - seen[status ^ (1 << a)])
            if status in seen:
                res = max(res, i - seen[status])
            else:
                seen[status] = i
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        mask, res = 0, 1
        mask_pos = {0: -1}
        
        for i, c in enumerate(s):
            c = int(c)
            mask ^= (1 << c)
            for j in range(11):
                check_mask = 1023 & (mask ^ (1 << j))
                if check_mask in mask_pos:
                    res = max(res, i - mask_pos[check_mask])
            if mask in mask_pos:
                res = max(res, i - mask_pos[mask])
            else:
                mask_pos[mask] = i
        return res


class Solution:
    def longestAwesome(self, s: str) -> int:
        # We have 10 + 1 types of palindromes.
        # Use any number as the middle character, or don't have a middle character.
        n = len(s)
        seen = {0:-1}
        status = res = 0
        for i, c in enumerate(s):
            status ^= 1 << (ord(c) - ord('0'))
            for a in range(10):
                if status ^ (1 << a) in seen:
                    res = max(res, i - seen[status ^ (1 << a)])
            if status in seen:
                res = max(res, i - seen[status])
            else:
                seen[status] = i
        return res

class Solution:
    def longestAwesome(self, s: str) -> int:
        if s==s[::-1]: return len(s)
        pattern,re = 0,0
        exit = {pattern:-1}
        for i,num in enumerate(s):
            pattern ^= 1<<int(num)
            if pattern==0: 
                re = i+1
                continue
            for k in range(10):
                new_p = pattern^(1<<k)
                re = max(re,i-exit.get(new_p,i))
            re = max(re,i-exit.get(pattern,i))
            exit.setdefault(pattern,i)
        return re
                
                


class Solution:
    def longestAwesome(self, s: str) -> int:
        memo = {0:-1}
        max_len = 0
        mask = 0
        for i in range(len(s)):
            num = int(s[i])
            mask ^= (1 << num)
            if mask in memo:
                max_len = max(max_len, i - memo[mask])
            for j in range(10):
                if mask ^ (1 << j) in memo:
                    max_len = max(max_len, i - memo[mask ^ (1 << j)])
            if mask not in memo:
                memo[mask] = i
        return max_len