Given a string S, consisting of lowercase Latin characters [a-z]. Find out all the possible palindromes that can be generated using the letters of the string and print them in lexicographical order.
Example 1:
Input: S = abbab
Output:{ abbba babab }
Explanation: abbba and babab are two
possible string whoch are palindrome.
Example 2:
Input: S = abc
Output: {}
Explanation: No permutation is palindromic.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function all_palindromes() which takes string S as the input parameter and returns a list of strings which are palindrome in lexicographical order.
 
Expected Time Complexity: O(2^n)
Expected Space Complexity: O(2^n)
 
Constraints:
1 <= Length of string <= 20

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(2^n)
Expected Auxiliary Space: O(2^n)

Starter code:
#User function Template for python3



class Solution:

	def all_palindromes(self, s):

		# Code here

Solutions:
class Solution:

	def solve(self, cnt, k, n, curr):
		if k == n // 2:
			self.ans.append(''.join(curr))
			return
		for i in range(26):
			if cnt[i] >= 2:
				curr[k] = chr(ord('a') + i)
				curr[n - 1 - k] = curr[k]
				cnt[i] -= 2
				self.solve(cnt, k + 1, n, curr)
				cnt[i] += 2

	def all_palindromes(self, s):
		cnt = [0] * 26
		for c in s:
			cnt[ord(c) - ord('a')] += 1
		odd = 0
		c = ' '
		for i in range(26):
			if cnt[i] % 2 == 1:
				odd += 1
				c = chr(ord('a') + i)
		if odd > 1:
			return []
		self.ans = []
		n = len(s)
		curr = [' '] * n
		if odd == 1:
			curr[n // 2] = c
		self.solve(cnt, 0, n, curr)
		return self.ans


def rec(freq, res, ans, n, od, N):
	if len(res) == n:
		a = res
		a = a[::-1]
		if N % 2 == 1:
			res += od
		res += a
		ans.append(res)
		return
	for i in range(26):
		if freq[i] > 0:
			freq[i] -= 1
			rec(freq, res + chr(i + 97), ans, n, od, N)
			freq[i] += 1

class Solution:

	def all_palindromes(self, s):
		freq = [0] * 26
		for i in s:
			freq[ord(i) - ord('a')] += 1
		odd = 0
		od = 0
		for i in range(26):
			odd += freq[i] % 2
			if freq[i] % 2:
				od = i
			freq[i] = freq[i] // 2
		if odd > 1:
			return []
		ans = []
		rec(freq, '', ans, len(s) // 2, chr(od + 97), len(s))
		return ans


class Solution:

	def per(self, c, l, b, m):
		if c == len(l) - 1:
			e = ''.join(l)
			if e not in m:
				m[e] = 1
				b.append(e)
			return
		for i in range(c, len(l)):
			(l[i], l[c]) = (l[c], l[i])
			self.per(c + 1, l, b, m)
			(l[i], l[c]) = (l[c], l[i])

	def all_palindromes(self, s):
		b = []
		l = []
		t = {}
		for i in s:
			l.append(i)
			if i in t:
				t[i] += 1
			else:
				t[i] = 1
		f = 0
		a = []
		m = {}
		for i in t:
			a.append(i)
			if t[i] != 2:
				f = 1
				break
		d = []
		if f == 0:
			self.per(0, a, b, m)
			for i in b:
				d.append(i + i[::-1])
			d.sort()
			return d
		self.per(0, l, b, m)
		for i in b:
			if i == i[::-1]:
				d.append(i)
		d.sort()
		return d


class Solution:

	def permuteString(self, indx, l, odd, s, path, ans):
		if indx > l:
			rev = path[::-1]
			res = path
			if len(odd) >= 1:
				res += odd
			res += rev
			ans.append(res)
			return
		for ch in s:
			if s[ch] > 0:
				s[ch] -= 1
				self.permuteString(indx + 1, l, odd, s, path + ch, ans)
				s[ch] += 1

	def all_palindromes(self, s):
		ans = []
		count = {}
		for ch in s:
			count[ch] = 1 + count.get(ch, 0)
		ss = {}
		co = 0
		length = 0
		odd = ''
		for k in count:
			v = count[k]
			if v % 2 == 1:
				co += 1
				odd = k
			ss[k] = v // 2
			length += v // 2
		if co > 1:
			return ans
		else:
			self.permuteString(1, length, odd, ss, '', ans)
			ans.sort()
			return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.all_palindromes(s)
		print('{', end=' ')
		for i in ans:
			print(i, end=' ')
		print('}')


class Solution:

	def all_palindromes(self, s):
		dp = {}
		for char in s:
			dp[char] = 1 + dp.get(char, 0)
		flg = 0
		string = ''
		mid = ''
		for key in dp.keys():
			if dp[key] % 2 == 0:
				string += key * int(dp[key] // 2)
			else:
				flg += 1
				mid = key
				string += key * int((dp[key] - 1) // 2)
		if flg > 1:
			return []

		def pal(string):
			if not string:
				return ['']
			visit = set()
			res2 = []
			for i in range(len(string)):
				char = string[0]
				if char not in visit:
					res = pal(string[1:])
					for s in res:
						s += char
						res2.append(s)
				visit.add(char)
				string = string[1:] + char
			return res2
		res = []
		for string in pal(string):
			res.append(string + mid + string[::-1])
		return sorted(res)


class Solution:
	ans = list()

	def solve(self, i, los, ht, oddc, res):
		if i == los:
			rev = res[::-1]
			if oddc is None:
				self.ans.append(res + rev)
			else:
				self.ans.append(res + oddc + rev)
			return
		for (key, val) in ht.items():
			if ht[key] > 0:
				ht[key] -= 1
				self.solve(i + 1, los, ht, oddc, res + key)
				ht[key] += 1

	def all_palindromes(self, s):
		self.ans = list()
		ht = {}
		count_of_odd_string = 0
		for ch in s:
			if ch in ht:
				ht[ch] += 1
			else:
				ht[ch] = 1
		len_of_string = 0
		oddc = None
		for (key, val) in ht.items():
			if val % 2 == 1:
				oddc = key
				count_of_odd_string += 1
			ht[key] = val // 2
			len_of_string += val // 2
		if count_of_odd_string > 1:
			return []
		self.solve(0, len_of_string, ht, oddc, '')
		return sorted(self.ans)


class Solution:

	def all_palindromes(self, s):
		res = []

		def palin(ssf, l):
			nonlocal odd
			if len(ssf) == l:
				if odd:
					res.append(ssf + odd + ssf[::-1])
				else:
					res.append(ssf + ssf[::-1])
				return
			for i in h.keys():
				if h[i] > 0:
					h[i] -= 1
					palin(ssf + i, l)
					h[i] += 1
		h = {}
		l = 0
		odd = None
		for i in s:
			h[i] = h.get(i, 0) + 1
		for i in h.keys():
			if odd and h[i] % 2:
				return []
			if not odd and h[i] % 2:
				odd = i
			h[i] = h[i] // 2
			l += h[i]
		palin('', l)
		res.sort()
		return res


class Solution:

	def all_palindromes(self, s):
		from collections import Counter
		c = Counter(s)
		ret = []

		def bt(stringSoFar, c):
			if len(c) == 0:
				x = ''.join(stringSoFar)
				y = ''.join(stringSoFar[::-1])
				ret.append(x + y)
				return
			if len(c) == 1:
				x = ''.join(stringSoFar)
				y = ''.join(stringSoFar[::-1])
				for (k, v) in c.items():
					ret.append(x + k * v + y)
					return
			t = list(c.items())
			for (k, v) in t:
				if v > 1:
					stringSoFar.append(k)
					c[k] -= 2
					if c[k] == 0:
						c.pop(k)
					bt(stringSoFar, c)
					stringSoFar.pop()
					if k not in c:
						c[k] = 0
					c[k] += 2
		bt([], c)
		ret.sort()
		return ret


class Solution:

	def all_palindromes(self, s):
		n = len(s)
		arr = [0] * 26
		for i in s:
			arr[ord(i) - ord('a')] += 1
		if not self.possible(arr, len(s)):
			return []
		odd = self.findmiddle(arr)
		final = ''
		(first, second) = ('', '')
		for i in range(26):
			if arr[i] != 0:
				ch = chr(i + ord('a'))
				ch = ch * (arr[i] // 2)
				first += ch
				second = ch + second
		new = first + odd + second
		res = [new]
		for _ in range(2 ** n):
			new = self.nextPalin(new)
			if len(new) == 0:
				break
			res.append(new)
		return res

	def possible(self, arr, ln):
		count = 0
		for i in arr:
			if i % 2 != 0:
				count += 1
		if ln % 2 == 0:
			return count == 0
		else:
			return count == 1

	def findmiddle(self, arr):
		for i in range(26):
			if arr[i] % 2 != 0:
				arr[i] -= 1
				return chr(i + ord('a'))
		return ''

	def nextPalin(self, N):
		if len(N) <= 3:
			return ''
		mid = len(N) // 2
		odd = N[mid] if len(N) % 2 == 1 else ''
		s = N[:mid]
		nums = list(s)
		n = len(nums)
		i = n - 2
		while i >= 0 and nums[i] >= nums[i + 1]:
			i -= 1
		if i < 0:
			return ''
		else:
			(l, r) = (i + 1, n - 1)
			while l < r:
				mid = (l + r) // 2 + 1
				if nums[mid] <= nums[i]:
					r = mid - 1
				else:
					l = mid
			(nums[i], nums[l]) = (nums[l], nums[i])
			(l, r) = (i + 1, n - 1)
			while l < r:
				(nums[l], nums[r]) = (nums[r], nums[l])
				l += 1
				r -= 1
			new = ''.join(nums)
			return new + odd + new[::-1]


class Solution:

	def all_palindromes(self, s):
		freq = [0] * 26
		ans = []

		def count_freq(s, f):
			count = 0
			for i in range(len(s)):
				f[ord(s[i]) - 97] += 1
			for i in f:
				if i % 2 == 1:
					count += 1
			if len(s) % 2 == 0 and count == 0 or (len(s) % 2 == 1 and count == 1):
				return (f, True)
			else:
				return (f, False)

		def half(s, freq):
			s1 = []
			oddc = ''
			i = 0
			while i < len(freq):
				if freq[i] != 0:
					if freq[i] % 2 == 0:
						s1.append(chr(i + 97) * (freq[i] // 2))
					elif freq[i] > 2:
						oddc = chr(i + 97)
						s1.append(chr(i + 97) * ((freq[i] - 1) // 2))
					else:
						oddc = chr(i + 97)
				i = i + 1
			pal = ''.join(s1)
			return (pal, oddc)

		def perm(s, p, oddc):
			if len(s) == 0:
				s1 = ''.join(p)
				s1 = s1 + oddc + s1[::-1]
				if s1 not in ans:
					ans.append(s1)
				return
			for i in range(len(s)):
				perm(s[0:i] + s[i + 1:], p + [s[i]], oddc)
			return
		(freq, ispalim) = count_freq(s, freq)
		if ispalim:
			(pattern, oddc) = half(s, freq)
			perm(pattern, [], oddc)
		return ans


class Solution:

	def func(self, map_s, oddchar, cs, ts, asf, ans_list):
		if cs == ts:
			ans_list.append(asf + oddchar + asf[::-1])
			return
		for i in map_s:
			if map_s[i] > 0:
				map_s[i] -= 1
				self.func(map_s, oddchar, cs + 1, ts, asf + i, ans_list)
				map_s[i] += 1

	def all_palindromes(self, s):
		map_s = {}
		for i in s:
			map_s[i] = map_s.get(i, 0) + 1
		oddcount = 0
		oddchar = ''
		for i in map_s:
			if map_s[i] % 2 == 1:
				oddcount += 1
				oddchar = i
			map_s[i] //= 2
		if oddcount > 1:
			return []
		ans_list = []
		self.func(map_s, oddchar, 0, len(s) // 2, '', ans_list)
		return sorted(ans_list)


from itertools import permutations

class Solution:

	def all_palindromes(self, s):
		d = {}
		for ch in s:
			d[ch] = d.get(ch, 0) + 1
		one_ch = ''
		hl = []
		for (k, v) in d.items():
			if v % 2 == 0:
				for i in range(v // 2):
					hl.append(k)
			elif one_ch == '':
				one_ch = k
				for i in range(v // 2):
					hl.append(k)
			else:
				return []
		hl.sort()
		perms = permutations(hl)
		op = []
		oc = set()
		for perm in perms:
			if perm in oc:
				continue
			oc.add(perm)
			hs = ''.join(perm)
			rs = ''.join(reversed(perm))
			op.append(hs + one_ch + rs)
		return op