Given a string S which only contains lowercase alphabets. Find the length of the longest substring of S such that the characters in it can be rearranged to form a palindrome. 
Example 1:
Input:
S = "aabe"
Output:
3
Explanation:
The substring "aab" can be rearranged to
"aba" which is the longest palindrome
possible for this String.
Example 2:
Input:
S = "adbabd"
Output:
6
Explanation:
The whole string “adbabd” can be
rearranged to form a palindromic substring.
One possible arrangement is "abddba".
Thus, output length of the string is 6. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function longestSubstring() which takes a String S as input and returns the length of largest possible Palindrome.
Expected Time Complexity: O(|S|*26)
Expected Auxiliary Space: O(|S|*26)
Constraints:
1 ≤ |S| ≤ 10^{5}

Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(|S|*26)
Expected Auxiliary Space: O(|S|*26)

Starter code:
#User function Template for python3



class Solution:

    def longestSubstring(self, S):

        # code here 

Solutions:
class Solution:

	def longestSubstring(self, s):
		ans = 1
		l = len(s)
		f = {0: -1}
		x = 0
		for i in range(l):
			z = ord(s[i]) - 97
			x = x ^ 1 << z
			if x in f:
				ans = max(ans, i - f[x])
			for j in range(26):
				t = x ^ 1 << j
				if t in f:
					ans = max(ans, i - f[t])
			if x not in f:
				f[x] = i
		return ans


class Solution:

	def longestSubstring(self, s):
		d = {}
		d[0] = -1
		x = ans = 0
		for i in range(len(s)):
			x = x ^ 1 << ord(s[i]) - ord('a')
			if x in d:
				ans = max(ans, i - d[x])
			else:
				d[x] = i
			for j in range(0, 26):
				m = x ^ 1 << j
				if m in d:
					ans = max(ans, i - d[m])
		return ans


class Solution:

	def longestSubstring(self, s):
		n = len(s)
		idx = {}
		ans = 0
		mask = 0
		idx[mask] = -1
		for i in range(n):
			temp = ord(s[i]) - 97
			mask ^= 1 << temp
			if mask in idx.keys():
				ans = max(ans, i - idx[mask])
			else:
				idx[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in idx.keys():
					if ans < i - idx[mask2]:
						ans = i - idx[mask2]
		return ans


class Solution:

	def longestSubstring(self, S):
		n = len(S)
		index = dict()
		answer = 0
		mask = 0
		index[mask] = -1
		for i in range(n):
			temp = ord(S[i]) - 97
			mask ^= 1 << temp
			if mask in index.keys():
				answer = max(answer, i - index[mask])
			else:
				index[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in index.keys():
					answer = max(answer, i - index[mask2])
		return answer


class Solution:

	def longestSubstring(self, s):
		ind = dict()
		ans = 0
		mask = 0
		ind[mask] = -1
		for i in range(len(s)):
			temp = ord(s[i]) - 97
			mask ^= 1 << temp
			if mask in ind:
				ans = max(ans, i - ind[mask])
			else:
				ind[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in ind:
					ans = max(ans, i - ind[mask2])
		return ans


class Solution:

	def longestSubstring(self, s):
		n = len(s)
		masks = {0: -1}

		def check(mask1, idx):
			res = 0
			if mask1 in masks:
				res = max(res, idx - masks[mask1])
			for i in range(26):
				mask2 = mask1 ^ 1 << i
				if mask2 in masks:
					res = max(res, idx - masks[mask2])
			return res
		(mask, ans) = (0, 0)
		for (i, c) in enumerate(s):
			mask ^= 1 << ord(c) - ord('a')
			ans = max(ans, check(mask, i))
			if mask not in masks:
				masks[mask] = i
		return ans


class Solution:

	def longestSubstring(self, S):
		length = 0
		mask = 0
		bitMap = {}
		bitMap[mask] = -1
		for i in range(len(S)):
			index = ord(S[i]) - 97
			mask = mask ^ 1 << index
			if mask in bitMap:
				length = max(length, i - bitMap[mask])
			else:
				bitMap[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in bitMap:
					length = max(length, i - bitMap[mask2])
		return length


import collections

class Solution:

	def longestSubstring(self, S):
		if not S:
			return
		ans = 1
		l = len(S)
		mp = {0: -1}
		x = 0
		for i in range(l):
			z = ord(S[i]) - ord('a')
			x = x ^ 1 << z
			if x in mp:
				ans = max(ans, i - mp[x])
			for j in range(26):
				t = x ^ 1 << j
				if t in mp:
					ans = max(ans, i - mp[t])
			if x not in mp:
				mp[x] = i
		return ans


class Solution:

	def is_palin(self, mapper, n):
		odd = 0
		for i in mapper.values():
			if i & 1:
				odd += 1
		if odd == 0:
			return True
		elif n & 1 and odd == 1:
			return True
		else:
			return False

	def front(self, mapper, s, n):
		for i in range(n):
			mapper[s[i]] -= 1
			if self.is_palin(mapper, n - i - 1):
				return n - i - 1
		return 1

	def ending(self, mapper, s, n):
		for i in range(n - 1, -1, -1):
			mapper[s[i]] -= 1
			if self.is_palin(mapper, i):
				return i
		return 1

	def both_side(self, mapper, s, n):
		i = 0
		j = n - 1
		while i < j:
			mapper[s[i]] -= 1
			mapper[s[j]] -= 1
			n -= 2
			if self.is_palin(mapper, n):
				return n
			i += 1
			j -= 1
		return 1

	def longestSubstring(self, s):
		n = len(s)
		mapper = dict()
		ans = 1
		l = len(s)
		f = {0: -1}
		x = 0
		for i in range(l):
			z = ord(s[i]) - 97
			x = x ^ 1 << z
			if x in f:
				ans = max(ans, i - f[x])
			for j in range(26):
				t = x ^ 1 << j
				if t in f:
					ans = max(ans, i - f[t])
			if x not in f:
				f[x] = i
		return ans
		maxi = -1000000000.0
		for i in range(n):
			mapper = dict()
			for j in range(i, n):
				mapper[s[j]] = 1 + mapper.get(s[j], 0)
				if self.is_palin(mapper, j - i + 1):
					maxi = max(maxi, j - i + 1)
		return maxi


class Solution:

	def longestSubstring(self, S):
		n = len(S)
		max_len = 0
		mp = {}
		mask = 0
		mp[mask] = -1
		for i in range(n):
			idx = ord(S[i]) - ord('a')
			mask = mask ^ 1 << idx
			if mask in mp:
				length = i - mp[mask]
				max_len = max(max_len, length)
			else:
				mp[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in mp:
					length = i - mp[mask2]
					max_len = max(max_len, length)
		return max_len


class Solution:

	def longestSubstring(self, S):
		dictt = {}
		dictt[0] = -1
		x = output = 0
		n = len(S)
		for i in range(n):
			x = x ^ 1 << ord(S[i]) - ord('a')
			if x in dictt:
				output = max(output, i - dictt[x])
			else:
				dictt[x] = i
			for j in range(0, 26):
				m = x ^ 1 << j
				if m in dictt:
					output = max(output, i - dictt[m])
		return output


class Solution:

	def longestSubstring(self, s):
		n = len(s)
		mp = dict()
		pr = 0
		sh = 0
		mp[sh] = -1
		for i in range(n):
			mrc = ord(s[i]) - 97
			sh ^= 1 << mrc
			if sh in mp.keys():
				pr = max(pr, i - mp[sh])
			else:
				mp[sh] = i
			for j in range(26):
				rs = sh ^ 1 << j
				if rs in mp.keys():
					pr = max(pr, i - mp[rs])
		return pr


from itertools import permutations

class Solution:

	def longestSubstring(self, S):
		ind = dict()
		ans = 0
		mas = 0
		ind[mas] = -1
		for i in range(len(S)):
			temp = ord(S[i]) - 97
			mas ^= 1 << temp
			if mas in ind.keys():
				ans = max(ans, i - ind[mas])
			else:
				ind[mas] = i
			for j in range(26):
				mask = mas ^ 1 << j
				if mask in ind.keys():
					ans = max(ans, i - ind[mask])
		return ans


class Solution:

	def longestSubstring(self, S):
		mask = 0
		mp = {}
		mp[0] = -1
		ans = 0
		for i in range(len(S)):
			o = ord(S[i]) - ord('a')
			mask ^= 1 << o
			if mask in mp:
				ans = max(ans, i - mp[mask])
			for j in range(26):
				nm = mask ^ 1 << j
				if nm in mp:
					ans = max(ans, i - mp[nm])
			if mask not in mp:
				mp[mask] = i
		return ans


class Solution:

	def longestSubstring(self, s):
		d = {}
		d[0] = -1
		x = ans = 0
		for i in range(len(s)):
			x = x ^ 1 << ord(s[i]) - ord('a')
			if x in d:
				ans = max(ans, i - d[x])
			else:
				d[x] = i
			for j in range(0, 26):
				m = x ^ 1 << j
				if m in d:
					ans = max(ans, i - d[m])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.longestSubstring(S))


class Solution:

	def longestSubstring(self, s):
		n = len(s)
		masks = {0: -1}

		def check(mask1, idx):
			res = 0
			if mask1 in masks:
				res = max(res, idx - masks[mask1])
			for i in range(26):
				mask2 = mask1 ^ 1 << i
				if mask2 in masks:
					res = max(res, idx - masks[mask2])
			return res
		(mask, ans) = (0, 0)
		for (i, c) in enumerate(s):
			mask ^= 1 << ord(c) - ord('a')
			ans = max(ans, check(mask, i))
			if mask not in masks:
				masks[mask] = i
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.longestSubstring(S))


class Solution:

	def longestSubstring(self, S):
		n = len(S)
		hash_map = {}
		mask = 0
		ans = 0
		hash_map[mask] = -1
		for i in range(n):
			tmp = ord(S[i]) - 97
			mask = mask ^ 1 << tmp
			if mask in hash_map.keys():
				ans = max(ans, i - hash_map[mask])
			else:
				hash_map[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in hash_map.keys():
					ans = max(ans, i - hash_map[mask2])
		return ans


class Solution:

	def longestSubstring(self, S):
		bit_mask = 0
		index_map = {}
		max_length = 0
		index_map[bit_mask] = -1
		for i in range(len(S)):
			c = ord(S[i]) - 97
			bit_mask ^= 1 << c
			if bit_mask in index_map:
				max_length = max(max_length, i - index_map[bit_mask])
			else:
				index_map[bit_mask] = i
			for j in range(26):
				bit_mask_2 = bit_mask ^ 1 << j
				if bit_mask_2 in index_map:
					max_length = max(max_length, i - index_map[bit_mask_2])
		return max_length


class Solution:

	def longestSubstring(self, S):
		index = dict()
		ans = 0
		m = 0
		index[m] = -1
		for i in range(len(S)):
			temp = ord(S[i]) - 97
			m = m ^ 1 << temp
			if m in index.keys():
				ans = max(ans, i - index[m])
			else:
				index[m] = i
			for j in range(26):
				mask2 = m ^ 1 << j
				if mask2 in index.keys():
					ans = max(ans, i - index[mask2])
		return ans


class Solution:

	def longestSubstring(self, S):
		n = len(S)
		m1 = 0
		m2 = 0
		ans = 0
		map = {0: -1}
		for i in range(n):
			idx = ord(S[i]) - ord('a')
			m1 = m1 ^ 1 << idx
			if m1 in map:
				ans = max(ans, i - map[m1])
			else:
				map[m1] = i
			for j in range(26):
				m2 = m1 ^ 1 << j
				if m2 in map:
					ans = max(ans, i - map[m2])
		return ans


class Solution:

	def longestSubstring(self, S):
		index = {0: -1}
		(mask, ans) = (0, 0)
		for i in range(len(S)):
			idx = ord(S[i]) - ord('a')
			mask ^= 1 << idx
			if mask in index:
				ans = max(ans, i - index[mask])
			else:
				index[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in index:
					ans = max(ans, i - index[mask2])
		return ans


class Solution:

	def longestSubstring(self, S):
		Dict = {0: -1}
		res = 0
		x = 0
		N = len(S)
		for i in range(N):
			num = ord(S[i]) - ord('a')
			x = x ^ 1 << num
			if x not in Dict:
				Dict[x] = i
			else:
				idx = Dict[x]
				res = max(res, i - Dict[x])
			for j in range(26):
				m = x ^ 1 << j
				if m in Dict:
					res = max(res, i - Dict[m])
		return res


class Solution:

	def longestSubstring(self, S):
		n = len(S)
		max_len = 0
		mask = 0
		pos_dict = {}
		pos_dict[0] = -1
		for i in range(n):
			bit_pos = ord(S[i]) - ord('a')
			mask = mask ^ 1 << bit_pos
			if mask in pos_dict:
				max_len = max(max_len, i - pos_dict[mask])
			else:
				pos_dict[mask] = i
			for j in range(26):
				mask2 = mask ^ 1 << j
				if mask2 in pos_dict:
					max_len = max(max_len, i - pos_dict[mask2])
		return max_len


class Solution:

	def longestSubstring(self, S):
		d = {}
		mask = 0
		d[mask] = -1
		res = 0
		for i in range(len(S)):
			ind = ord(S[i]) - 97
			mask ^= 1 << ind
			if mask in d:
				res = max(res, i - d[mask])
			else:
				d[mask] = i
			for j in range(26):
				newmask = mask ^ 1 << j
				if newmask in d:
					res = max(res, i - d[newmask])
		return res


class Solution:

	def longestSubstring(self, s):
		l = 0
		mask = 0
		mp = {}
		mp[mask] = -1
		for i in range(len(s)):
			ind = ord(s[i]) - 97
			mask ^= 1 << ind
			if mask in mp:
				l = max(l, i - mp[mask])
			else:
				mp[mask] = i
			for j in range(0, 26):
				mask2 = mask ^ 1 << j
				if mask2 in mp:
					l = max(l, i - mp[mask2])
		return l


class Solution:

	def longestSubstring(self, s):
		d = {}
		d[0] = -1
		flag = 0
		res = 0
		for i in range(len(s)):
			flag = flag ^ 1 << ord(s[i]) - ord('a')
			if flag in d:
				res = max(res, i - d[flag])
			else:
				d[flag] = i
			for j in range(26):
				mx = flag ^ 1 << j
				if mx in d:
					res = max(res, i - d[mx])
		return res


class Solution:

	def longestSubstring(self, S):
		ans = 0
		temp = 0
		has = dict()
		has[0] = -1
		for i in range(len(S)):
			t = ord(S[i]) - ord('a')
			temp ^= 1 << t
			if temp in has.keys():
				ans = max(ans, i - has[temp])
			else:
				has[temp] = i
			for j in range(26):
				temp2 = temp ^ 1 << j
				if temp2 in has.keys():
					ans = max(ans, i - has[temp2])
		return ans


class Solution:

	def longestSubstring(self, S):
		d = {}
		d[0] = -1
		x = ans = 0
		for i in range(len(S)):
			x = x ^ 1 << ord(S[i]) - ord('a')
			if x in d:
				ans = max(ans, i - d[x])
			else:
				d[x] = i
			for j in range(0, 26):
				m = x ^ 1 << j
				if m in d:
					ans = max(ans, i - d[m])
		return ans

	def permute(self, xs, low=0):
		if low + 1 >= len(xs):
			yield xs
		else:
			for p in self.permute(xs, low + 1):
				yield p
			for i in range(low + 1, len(xs)):
				(xs[low], xs[i]) = (xs[i], xs[low])
				for p in self.permute(xs, low + 1):
					yield p
				(xs[low], xs[i]) = (xs[i], xs[low])

	def isPalindrom(self, S):
		return S == S[::-1]


class Solution:

	def longestSubstring(self, s):
		d = {}
		(k, res) = (0, 0)
		d[0] = -1
		for i in range(len(s)):
			k = k ^ 1 << ord(s[i]) - 97
			if k in d:
				res = max(res, i - d[k])
			else:
				d[k] = i
			for j in range(26):
				temp = k ^ 1 << j
				if temp in d:
					res = max(res, i - d[temp])
		return res


class Solution:

	def longestSubstring(self, S):
		data = {}
		data[0] = -1
		(temp, res) = (0, 0)
		for i in range(len(S)):
			temp = temp ^ 1 << ord(S[i]) - ord('a')
			if temp in data:
				res = max(res, i - data[temp])
			else:
				data[temp] = i
			for j in range(26):
				k = temp ^ 1 << j
				if k in data:
					res = max(res, i - data[k])
		return res


class Solution:

	def longestSubstring(self, S):
		mask = 0
		d = {0: -1}
		ans = 0
		for (i, c) in enumerate(S):
			bit = ord(c) - ord('a')
			mask ^= 1 << bit
			if mask in d:
				ans = max(ans, i - d[mask])
			for j in range(26):
				if mask ^ 1 << j in d:
					ans = max(ans, i - d[mask ^ 1 << j])
			if mask not in d:
				d[mask] = i
		return ans


class Solution:

	def longestSubstring(self, s):
		d = {}
		d[0] = -1
		x = ans = 0
		for i in range(len(s)):
			x = x ^ 1 << ord(s[i]) - ord('a')
			if x in d:
				ans = max(ans, i - d[x])
			else:
				d[x] = i
			for j in range(0, 26):
				m = x ^ 1 << j
				if m in d:
					ans = max(ans, i - d[m])
		return ans

def palindrome(S):
	dict_ = {}
	for i in S:
		if i in dict_:
			dict_[i] += 1
		else:
			dict_[i] = 1
	max = 0
	for i in dict_:
		if dict_[i] % 2 != 0:
			max += 1
		if max > 1:
			return False
	return True