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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Data structures

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:
		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])
		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])
				elif 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')
			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


class Solution:

	def longestAwesome(self, s: str) -> int:
		bd = {}
		bd[0] = -1
		soen = 0
		for (i, n) in enumerate(s):
			soen ^= 1 << int(n)
			bd[soen] = -1
			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:
		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:

	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: 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])
			for j in range(10):
				tmp = mask ^ 1 << j
				if best < i - prev[tmp] + 1:
					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:

		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:
				maskDict[mask] = idx
		return ans


class Solution:

	def longestAwesome(self, s: str) -> int:
		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])
		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
		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 = {}
	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()
			if key in presum:
				res = max(res, i - presum[key])
			for x in range(10):
				newKey = key
				if key >> x & 1:
					newKey -= 1 << x
				else:
					newKey |= 1 << x
				if newKey in presum:
					res = max(res, i - presum[newKey])
			if key not in presum:
				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:

	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
			if mask in pos:
				len = n - pos[mask]
				if len % 2 == 0:
					ans = max(ans, len)
			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])
			for try_xor in xors:
				prev_xor = cur_xor ^ try_xor
				if first_pos[prev_xor] != -1:
					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')
			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)
			if mask not in list(F.keys()):
				F[mask] = j
		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])
			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


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 = {}
		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:
				ans = max(ans, i - dp[state])
			for num in range(10):
				if state ^ 1 << num in dp:
					ans = max(ans, i - dp[state ^ 1 << num])
		return ans


class Solution:

	def longestAwesome(self, s: str) -> int:
		idxs = [1000000000.0 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 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:
		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:
		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


from collections import defaultdict

class Solution:

	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


class Solution:

	def longestAwesome(self, s: str) -> int:
		pattern = 0
		d = {pattern: -1}
		res = 0
		for (cur_i, x) in enumerate(s):
			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 = [0] * len(s)
		seen = {0: -1}
		for i in range(0, len(s)):
			d = ord(s[i]) - ord('0')
			p[i] = 1 << d ^ p[i - 1]
			for od in range(10):
				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:
		(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


from typing import List

class Solution:

	def longestAwesome(self, s: str) -> int:
		res = 0
		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]
				res = max(res, cur_i - existing.get(tuple(new_pattern), cur_i))
			res = max(res, cur_i - existing.get(tuple(pattern), cur_i))
			existing.setdefault(tuple(pattern), cur_i)
		return res


class Solution:

	def longestAwesome(self, s: str) -> int:
		sLength = len(s)
		earliestBinaries = {}
		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 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:

	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


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


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
		d = {tuple(pattern): -1}
		res = 0
		for (i, x) in enumerate(s):
			num = int(x)
			pattern[num] = not pattern[num]
			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]
				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 : 1e+20)
		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])
		return ans


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:
		n = len(s)
		(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:
		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:
		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

	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())
		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
			if loc[sofar] > -2:
				ans = max(ans, idx - loc[sofar])
			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):
			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:

	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:

	def longestAwesome(self, s: str) -> int:
		n = len(s)
		res = mask = 0
		seen = [n] * 1024
		seen[0] = -1
		for i in range(n):
			mask ^= 1 << int(s[i])
			res = max(res, i - seen[mask])
			for num in range(10):
				res = max(res, i - seen[mask ^ 1 << num])
			seen[mask] = min(seen[mask], i)
		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


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:
		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
			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:
		seen = {0: -1}
		max_len = 0
		n = 0
		for i in range(len(s)):
			digit = int(s[i])
			n = n ^ 1 << digit
			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)
			res = max(res, i - seen[mask])
			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:
		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:
		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:
		index = [-1] + [len(s)] * 1023
		(prefix, ans) = (0, 0)
		for (i, c) in enumerate(s):
			prefix = prefix ^ 1 << ord(c) - ord('0')
			print(prefix)
			ans = max(ans, i - index[prefix])
			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:
		d = 0
		m = 0
		l = []
		l.append(d)
		dd = {}
		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)]
		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:
					m = max(abs(dd[j][0] - dd[i][1]), m)
					m = max(abs(dd[j][1] - dd[i][0]), m)
		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:
		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:

	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}
		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)
		if n <= 1:
			return n
		dp = [-1] + [n] * 1023
		(mask, res) = (0, 0)
		for i in range(n):
			mask = mask ^ 1 << int(s[i])
			for j in range(11):
				ch_mask = 1023 & (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
			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:
		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}
		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])
			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:

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


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
			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)
				anss.append(isPalindrome(dic, numbers[i - l + 1], r_num))
			return (max(anss), cur_max)
		(numbers, counts) = compact(s)
		cur_max = 0
		for l in range(len(numbers), 0, -1):
			(new_max, max_acc) = rollingHash(numbers, counts, l)
			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:

		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):
			mask ^= 1 << ord(ch) - ord('0')
			if mask in mask_dict:
				max_length = max(max_length, i - mask_dict[mask])
			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:
		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:
		m = [100000.0 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:
		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