Given a String S, Find all possible Palindromic partitions of the given String.
 
Example 1:
Input:
S = "geeks"
Output:
g e e k s
g ee k s
Explanation:
All possible palindromic partitions
are printed.
Example 2:
Input:
S = "madam"
Output:
m a d a m
m ada m
madam
Your Task:
You don't need to read input or print anything. Your task is to complete the function allPalindromicPerms() which takes a String S as input parameter and returns a list of lists denoting all the possible palindromic partitions in the order of their appearance in the original string.
 
Expected Time Complexity: O(N*2^{N})
Expected Auxiliary Space: O(N^{2}), where N is the length of the String
 
Constraints:
1 <= |S| <= 20

Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Complete search
Skill types: Dynamic programming

Data structures

Complete search
Expected Time Complexity: O(N*2^{N})
Expected Auxiliary Space: O(N^{2}), where N is the length of the String

Starter code:
#User function Template for python3

class Solution:
    def allPalindromicPerms(self, S):
        # code here 

Solutions:
class Solution:

	def allPalindromicPerms(self, S):

		def func(index, s, path, res):
			if index == len(s):
				res.append([ele for ele in path])
				return
			for i in range(index, len(s)):
				if isPalindrome(s, index, i):
					path.append(s[index:i + 1])
					func(i + 1, s, path, res)
					path.pop()

		def isPalindrome(s, start, end):
			while start <= end:
				if s[start] != s[end]:
					return False
				start += 1
				end -= 1
			return True
		res = []
		path = []
		func(0, S, path, res)
		return res


class Solution:

	def allPalindromicPerms(self, S):
		ans = []
		temp = []

		def palli(S, start, end):
			sub = S[start:end]
			return sub == sub[::-1]

		def func(i, S, temp, ans):
			if i == len(S):
				ans.append(temp[:])
			for j in range(i, len(S)):
				if palli(S, i, j + 1):
					temp.append(S[i:j + 1])
					func(j + 1, S, temp, ans)
					temp.pop()
		func(0, S, temp, ans)
		return ans


def ispalindrome(s, ind, i):
	x = ind
	y = i
	while x < y:
		if s[x] != s[y]:
			return False
		x += 1
		y -= 1
	return True

def palinpart(s, ind, n, ans, subs):
	if ind == n:
		ans.append(subs[:])
		return
	temp = ''
	for i in range(ind, n):
		temp += s[i]
		if ispalindrome(s, ind, i):
			subs.append(temp)
			palinpart(s, i + 1, n, ans, subs)
			subs.pop()

class Solution:

	def allPalindromicPerms(self, s):
		ans = []
		subs = []
		n = len(s)
		i = 0
		palinpart(s, i, n, ans, subs)
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		ans = []
		res = []

		def isPali(s):
			n = len(s)
			for i in range(n // 2):
				if s[i] != s[n - i - 1]:
					return False
			return True

		def bts(i):
			if i == n:
				res.append(ans[:])
				return
			for index in range(i, n):
				if isPali(S[i:index + 1]):
					ans.append(S[i:index + 1])
					bts(index + 1)
					ans.pop()
		bts(0)
		return res


class Solution:

	def allPalindromicPerms(self, S):

		def helper(index, s, temp, ans):
			if index == len(s):
				ans.append([ele for ele in temp])
				return
			for i in range(index, len(s)):
				if isPalindrome(s, index, i):
					temp.append(s[index:i + 1])
					helper(i + 1, s, temp, ans)
					temp.pop()

		def isPalindrome(s, start, end):
			while start <= end:
				if s[start] != s[end]:
					return False
				start += 1
				end -= 1
			return True
		ans = []
		temp = []
		helper(0, S, temp, ans)
		return ans


class Solution:

	def is_palindrome(self, data):
		(i, j) = (0, len(data) - 1)
		while i < j:
			if data[i] != data[j]:
				return False
			i += 1
			j -= 1
		return True

	def solve(self, start, S, palindromes, ans):
		if start >= len(S):
			ans.append(palindromes[:])
			return
		for i in range(start, len(S)):
			if self.is_palindrome(S[start:i + 1]):
				palindromes.append(S[start:i + 1])
				self.solve(i + 1, S, palindromes, ans)
				palindromes.pop()

	def allPalindromicPerms(self, S):
		ans = []
		palindromes = []
		self.solve(0, S, palindromes, ans)
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		r = []

		def subs(st, out):
			if st == n:
				r.append(out)
				return
			for i in range(st, n):
				if S[st:i + 1] == S[st:i + 1][::-1]:
					subs(i + 1, out + [S[st:i + 1]])
		subs(0, [])
		return r


class Solution:

	def allPalindromicPerms(self, S):
		a = list(S)
		ans = set()

		def solve(a):
			ans.add(tuple(a))
			if len(a) <= 1:
				return
			for i in range(1, len(a)):
				if a[i - 1] == a[i]:
					b = a[:i - 1] + [a[i - 1] + a[i]] + a[i + 1:]
					solve(b)
				if i + 1 < len(a) and a[i - 1] == a[i + 1]:
					c = a[:i - 1] + [a[i - 1] + a[i] + a[i + 1]] + a[i + 2:]
					solve(c)
		solve(a)
		return sorted(list(ans))


class Solution:

	def isPalindrome(self, s):
		n = len(s)
		for i in range((n + 1) // 2):
			if s[i] != s[n - 1 - i]:
				return 0
		return 1

	def util(self, s, ans):
		global a
		if len(s) == 0:
			a[ans] = 1
			print(ans)
			return
		for k in range(1, len(s) + 1):
			if self.isPalindrome(s[:k]) == 1:
				if len(ans) == 0:
					self.util(s[k:], ans + s[:k])
				else:
					self.util(s[k:], ans + ' ' + s[:k])

	def allPalindromicPerms(self, S):
		global a
		a = {}
		self.util(S, '')
		return []


class Solution:

	def allPalindromicPerms(self, S):
		l = []

		def back(start, c):
			if start == len(S):
				l.append(c)
			for i in range(start, len(S)):
				if S[start:i + 1] == S[start:i + 1][::-1]:
					back(i + 1, c + [S[start:i + 1]])
		back(0, [])
		return l


class Solution:

	def allPalindromicPerms(self, S):
		self.res = set()
		self.solve(list(S))
		return sorted(list(self.res))

	def solve(self, arr):
		self.res.add(tuple(arr))
		if len(arr) <= 1:
			return
		for i in range(1, len(arr)):
			if arr[i - 1] == arr[i][::-1]:
				brr = arr[:i - 1] + [arr[i - 1] + arr[i]] + arr[i + 1:]
				self.solve(brr)
			if i + 1 < len(arr) and arr[i - 1] == arr[i + 1][::-1]:
				brr = arr[:i - 1] + [arr[i - 1] + arr[i] + arr[i + 1]] + arr[i + 2:]
				self.solve(brr)


class Solution:

	def allPalindromicPerms(self, S):
		l = []

		def bac(start, curl):
			if start == len(S):
				l.append(curl)
			for i in range(start, len(S)):
				if S[start:i + 1] == S[start:i + 1][::-1]:
					bac(i + 1, curl + [S[start:i + 1]])
		bac(0, [])
		return l


def palindromic_partition_helper(input_string: str, output_string: str, result_arr: []):
	if len(input_string) == 0:
		result_arr.append(output_string)
		return
	n = len(input_string)
	for i in range(0, n):
		word = input_string[0:i + 1]
		ros = input_string[i + 1:]
		if is_palindrome(word):
			output_string = output_string + word + '-'
			palindromic_partition_helper(ros, output_string, result_arr)
			output_string = output_string[:-(len(word) + 1)]

def is_palindrome(word):
	start = 0
	end = len(word) - 1
	while start < end:
		if word[start] != word[end]:
			return False
		start = start + 1
		end = end - 1
	return True

def print_partition(input_word):
	result_arr = []
	input_dict = {}
	palindromic_partition_helper(input_word, '', result_arr)
	final_arr = []
	for data in result_arr:
		sub_string = data.split('-')[:-1]
		final_arr.append(sub_string)
	return final_arr

class Solution:

	def allPalindromicPerms(self, S):
		return print_partition(S)


class Solution:

	def allPalindromicPerms(self, s):
		res = []
		part = []

		def ispalin(i, j):
			while i < j:
				if s[i] != s[j]:
					return False
				i += 1
				j -= 1
			return True

		def dfs(i):
			if i == len(s):
				res.append(part.copy())
			for j in range(i, len(s)):
				if ispalin(i, j):
					part.append(s[i:j + 1])
					dfs(j + 1)
					part.pop()
		dfs(0)
		return res


class Solution:

	def allPalindromicPerms(self, S):
		s = S
		n = len(s)
		(ds, ans) = ([], [])

		def ispalindrome(start, end, s):
			while start <= end:
				if s[start] != s[end]:
					return False
				start += 1
				end -= 1
			return True

		def rec(idx, s):
			if idx == n:
				ans.append(list(ds))
				return ans
			for i in range(idx, n):
				if ispalindrome(idx, i, s):
					ds.append(s[idx:i + 1])
					rec(i + 1, s)
					ds.pop()
			return ans
		return rec(0, s)


class Solution:

	def allPalindromicPerms(self, S):
		result = []
		temp = []
		n = len(S)
		self.Util(0, S, temp, result, n)
		return result

	def Util(self, index, S, temp, result, n):
		if index == n:
			result.append(temp[:])
			return
		for i in range(index, n):
			if self.isPalin(index, i, S):
				temp.append(S[index:i + 1])
				self.Util(i + 1, S, temp, result, n)
				temp.pop()

	def isPalin(self, s, e, S):
		while s <= e:
			if S[s] != S[e]:
				return False
			s += 1
			e -= 1
		return True


class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		res = []

		def subs(start, out):
			if start == n:
				res.append(out)
				return
			for i in range(start, n):
				if S[start:i + 1] == S[start:i + 1][::-1]:
					subs(i + 1, out + [S[start:i + 1]])
		subs(0, [])
		return res


class Solution:

	def allPalindromicPerms(self, S):

		def palind(f):
			l = len(f)
			for i in range(l // 2):
				if f[i] != f[l - i - 1]:
					return 0
			return 1

		def manu(i, n, f, s):
			if i == n:
				x = []
				for i in range(len(f)):
					x.append(f[i])
				a.append(x)
				return 0
			x = ''
			for j in range(i, n):
				x += s[j]
				if palind(x):
					f.append(x)
					manu(j + 1, n, f, s)
					f.pop()
			return
		a = []
		manu(0, len(S), [], S)
		return a


def isPalindrome(string: str, low: int, high: int):
	while low < high:
		if string[low] != string[high]:
			return False
		low += 1
		high -= 1
	return True

def allPalPartUtil(allPart: list, currPart: list, start: int, n: int, string: str):
	if start >= n:
		x = currPart.copy()
		allPart.append(x)
		return
	for i in range(start, n):
		if isPalindrome(string, start, i):
			currPart.append(string[start:i + 1])
			allPalPartUtil(allPart, currPart, i + 1, n, string)
			currPart.pop()

class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		allPart = []
		currPart = []
		allPalPartUtil(allPart, currPart, 0, n, S)
		return allPart


class Solution:

	def allPalindromicPerms(self, S):

		def backtrack(start, currl):
			if start == len(S):
				res.append(currl)
			for i in range(start, len(S)):
				if S[start:i + 1] == S[start:i + 1][::-1]:
					backtrack(i + 1, currl + [S[start:i + 1]])
		res = []
		backtrack(0, [])
		return res


def rec(S, ind, res, string):
	if ind == len(S):
		res.append(list(string.split()))
	ans = 0
	for i in range(ind + 1, len(S) + 1):
		temp = S[ind:i]
		if temp == temp[::-1]:
			rec(S, i, res, string + ' ' + temp)

class Solution:

	def allPalindromicPerms(self, S):
		res = []
		rec(S, 0, res, '')
		return res


class Solution:

	def allPalindromicPerms(self, S):
		res = []
		perm = []

		def dfs(i):
			if i >= len(S):
				res.append(perm.copy())
				return
			for j in range(i, len(S)):
				if self.isPali(S, i, j):
					perm.append(S[i:j + 1])
					dfs(j + 1)
					perm.pop()
		dfs(0)
		return res

	def isPali(self, s, l, r):
		while l < r:
			if s[l] != s[r]:
				return False
			l = l + 1
			r = r - 1
		return True


class Solution:

	def allPalindromicPerms(self, S):
		s = S
		res = []

		def check(s, start, end):
			while start <= end:
				if s[start] != s[end]:
					return False
				start += 1
				end -= 1
			return True

		def f(s, ind, ds, res):
			if ind == len(s):
				res.append(ds.copy())
				return
			for i in range(ind, len(s)):
				if check(s, ind, i):
					ds.append(s[ind:i + 1])
					f(s, i + 1, ds, res)
					ds.pop()
			return res
		return f(s, 0, [], res)


from collections import defaultdict as dd

class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		palindromes = dd(lambda : [])
		for i in range(n):
			j = 0
			while i - j >= 0 and i + 2 + j <= n:
				s = S[i - j:i + 2 + j]
				if s == s[::-1]:
					palindromes[i - j].append(s)
				else:
					break
				j += 1
		for i in range(n):
			j = 0
			while i - j >= 0 and i + 1 + j <= n:
				s = S[i - j:i + 1 + j]
				if s == s[::-1]:
					palindromes[i - j].append(s)
				else:
					break
				j += 1
		output = []
		stack = []
		for item in palindromes[0]:
			stack.append((item, 0))
		while stack:
			(item, i) = stack.pop()
			if len(item) - i == n:
				output.append([item])
				continue
			for pali in palindromes[len(item) - i]:
				stack.append((item + ' ' + pali, i + 1))
		return sorted(output)


class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		res = []
		curr = []
		self.allpartitions(S, res, curr, 0)
		return res

	def allpartitions(self, s, res, curr, start):
		n = len(s)
		if start >= n:
			x = curr.copy()
			res.append(x)
			return
		for i in range(start, n):
			if self.ispalindrome(s, start, i):
				curr.append(s[start:i + 1])
				self.allpartitions(s, res, curr, i + 1)
				curr.pop()

	def ispalindrome(self, string, low, high):
		while low < high:
			if string[low] != string[high]:
				return False
			low += 1
			high -= 1
		return True


class Solution:

	def allPalindromicPerms(self, S):
		result = []
		temp = []
		index = 0
		self.solve(index, S, temp, result)
		return result

	def solve(self, index, s, temp, result):
		if index == len(s):
			result.append(temp[:])
			return
		for i in range(index, len(s)):
			if self.checkPal(index, i, s):
				temp.append(s[index:i + 1])
				self.solve(i + 1, s, temp, result)
				temp.pop()

	def checkPal(self, s, e, S):
		while s <= e:
			if S[s] != S[e]:
				return False
			s += 1
			e -= 1
		return True


class Solution:

	def ispalindrome(self, s, start, end):
		while start <= end:
			if s[start] != s[end]:
				return False
			start += 1
			end -= 1
		return True

	def solve(self, idx, s, ans, path):
		if idx == len(s):
			ans.append(path.copy())
			return
		for i in range(idx, len(s)):
			if self.ispalindrome(s, idx, i):
				path.append(s[idx:i + 1])
				self.solve(i + 1, s, ans, path)
				path.pop()

	def allPalindromicPerms(self, s):
		ans = []
		path = []
		self.solve(0, s, ans, path)
		return ans


def func(s, temp, ans):
	if not s:
		ans.append(temp[:])
		return
	for i in range(1, len(s) + 1):
		t = s[:i]
		if t == t[::-1]:
			func(s[i:], temp + [t], ans)

class Solution:

	def allPalindromicPerms(self, s):
		ans = []
		func(s, [], ans)
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		self.res = []
		self.n = len(S)
		self.pals = self.palindrome(S)
		curr = []
		self.palsTmp(curr, 0, S)
		return self.res

	def palsTmp(self, curr, i, S):
		if i >= self.n:
			self.res.append(list(curr))
		else:
			for j in range(i, self.n):
				if self.pals[i][j]:
					curr.append(S[i:j + 1])
					self.palsTmp(curr, j + 1, S)
					curr.pop()

	def palindrome(self, s):
		n = len(s)
		tb = [[False for j in range(n)] for i in range(n)]
		for i in range(n):
			tb[i][i] = True
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				tb[i][i + 1] = True
		for gap in range(2, n):
			for i in range(n - gap):
				j = i + gap
				if s[i] == s[j] and tb[i + 1][j - 1]:
					tb[i][j] = True
		return tb


class Solution:

	def allPalindromicPerms(self, S):
		res = []
		part = []
		n = len(S)

		def dfs(i):
			if i >= n:
				res.append(part[:])
				return
			for j in range(i, n):
				if self.isPalindrome(S, i, j):
					part.append(S[i:j + 1])
					dfs(j + 1)
					part.pop()
			return res
		return dfs(0)

	def isPalindrome(self, S, i, j):
		if S[i:j + 1] == S[i:j + 1][::-1]:
			return True
		else:
			return False


class Solution:

	def allPalindromicPerms(self, S):

		def isPalindrome(i, j, S):
			while i <= j:
				if S[i] != S[j]:
					return False
				i += 1
				j -= 1
			return True

		def helper(i, arr, ans):
			if i == len(S):
				ans.append(arr[:])
				return
			for j in range(i, len(S)):
				if isPalindrome(i, j, S):
					arr.append(S[i:j + 1])
					helper(j + 1, arr, ans)
					arr.pop()
		(arr, ans) = ([], [])
		helper(0, arr, ans)
		return ans


def expandByCenter(S, n, c1, c2, graph):
	while c1 >= 0 and c2 < n and (S[c1] == S[c2]):
		graph[c1].add(c2)
		c1 -= 1
		c2 += 1

def util(graph, S, n, u, ans, path):
	if u == n:
		path.append(n)
		li = []
		for i in range(len(path) - 1):
			li.append(S[path[i]:path[i + 1]])
		ans.append(li)
		path.pop()
		return
	path.append(u)
	for v in sorted(graph[u]):
		util(graph, S, n, v + 1, ans, path)
	path.pop()

class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		graph = {u: set() for u in range(n)}
		for c1 in range(n):
			expandByCenter(S, n, c1, c1, graph)
			expandByCenter(S, n, c1, c1 + 1, graph)
		ans = []
		util(graph, S, n, 0, ans, [])
		return ans


class Solution:

	def isPalin(self, s):
		n = len(s)
		i = 0
		j = n - 1
		while i <= j:
			if s[i] != s[j]:
				return 0
			i += 1
			j -= 1
		return 1

	def solve(self, inp, out, ans):
		if len(inp) == 0:
			ans.append(out.copy())
			return
		n = len(inp)
		for i in range(n):
			if self.isPalin(inp[:i + 1]):
				out.append(inp[:i + 1])
				self.solve(inp[i + 1:], out, ans)
				out.pop()

	def allPalindromicPerms(self, S):
		n = len(S)
		ans = []
		inp = S
		out = []
		self.solve(inp, out, ans)
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		res = []
		n = len(S)

		def dfs(index, l):
			if index == n:
				res.append(l.copy())
				return
			for i in range(index, n):
				s1 = S[index:i + 1]
				if s1 == s1[::-1]:
					l.append(s1)
					dfs(i + 1, l)
					l.pop()
			return res
		res = dfs(0, [])
		return res


class Solution:

	def allPalindromicPerms(self, S):

		def isPalindrom(si, ei):
			nonlocal S
			for i in range((ei - si + 1) // 2):
				if S[si + i] != S[ei - i]:
					return False
			return True
		ans = []
		n = len(S)

		def backtrack(starti, arr):
			nonlocal S, ans, n
			if starti == n:
				ans.append(arr.copy())
			else:
				for endi in range(starti, n):
					if isPalindrom(starti, endi):
						arr.append(S[starti:endi + 1])
						backtrack(endi + 1, arr)
						arr.pop()
		backtrack(0, [])
		return ans


class Solution:

	def __init__(self):
		self.dp = dict()

	def isPalin(self, s):
		return s == s[::-1]

	def allPalindromicPerms(self, s, i=0):
		if len(s) == 1:
			return [s]
		if self.dp.get(s) != None:
			return self.dp[s]
		till = ''
		way = []
		if self.isPalin(s):
			way.append([s])
		for x in range(1, len(s)):
			rem = s[:x]
			if not self.isPalin(rem):
				continue
			for _ in self.allPalindromicPerms(s[x:], i + 1):
				way.append([rem, *_])
		self.dp[s] = way
		if i == 0:
			return sorted(way)
		return way


class Solution:

	def allPalindromicPerms(self, S):
		(res, curr, i, n) = ([], [], 0, len(S))
		pals = self.isPal(S)
		self.palPermsTmp(curr, i, res, n, S, pals)
		return res

	def palPermsTmp(self, curr, i, res, n, s, pals):
		if i >= n:
			res.append(list(curr))
		else:
			for j in range(i, n):
				if pals[i][j]:
					curr.append(s[i:j + 1])
					self.palPermsTmp(curr, j + 1, res, n, s, pals)
					curr.pop()

	def isPal(self, s):
		n = len(s)
		pals = [[False for i in range(n)] for j in range(n)]
		for j in range(n):
			pals[j][j] = True
		for j in range(n - 1):
			pals[j][j + 1] = s[j] == s[j + 1]
		for gap in range(2, n):
			for j in range(n - gap):
				i = j + gap
				pals[j][i] = (s[j] == s[i]) & pals[j + 1][i - 1]
		return pals


class Solution:

	def allPalindromicPerms(self, S):

		def helper(s, v):
			if s == n:
				ans.append(v)
				return
			for i in range(s, n):
				if S[s:i + 1] == S[s:i + 1][::-1]:
					helper(i + 1, v + [S[s:i + 1]])
		ans = []
		n = len(S)
		helper(0, [])
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		self.s = S
		self.n = len(S)
		self.palindromes = []
		self.findPalindromes(0, '', [])
		return self.palindromes

	def findPalindromes(self, index, word, palindrome):
		if index >= self.n:
			if word == '':
				self.palindromes.append(palindrome.copy())
			return
		word += self.s[index]
		if word == word[::-1]:
			self.findPalindromes(index + 1, '', palindrome + [word])
		self.findPalindromes(index + 1, word, palindrome)


class Solution:

	def allPalindromicPerms(self, s):

		def check(strs):
			return strs == strs[::-1]
		ans = []

		def fun(temp, t):
			nonlocal ans
			if len(t) == 0:
				ans.append(temp)
				return
			for gap in range(1, len(t) + 1):
				sub_t = t[:gap]
				if check(sub_t):
					fun(temp + [sub_t], t[gap:])
				else:
					continue
		fun([], s)
		return ans


class Solution:

	def allPalindromicPerms(self, S):

		def helper(ind, s, sub, res):
			if ind == len(s):
				res.append([i for i in sub])
				return
			for i in range(ind, len(s)):
				if ispal(s, ind, i):
					sub.append(s[ind:i + 1])
					helper(i + 1, s, sub, res)
					sub.pop()

		def ispal(s, start, end):
			while start <= end:
				if s[start] != s[end]:
					return False
				start += 1
				end -= 1
			return True
		res = []
		sub = []
		helper(0, S, sub, res)
		return res


class Solution:

	def allPalindromicPerms(self, S):
		s = S

		def palindrome(sub):
			lt = 0
			rt = len(sub) - 1
			while lt < rt:
				if sub[lt] != sub[rt]:
					return False
				lt += 1
				rt -= 1
			return True

		def part(index, s, temp, ans):
			if index == len(s):
				ans.append(temp.copy())
				return
			else:
				for i in range(index, len(s)):
					sub = s[index:i + 1]
					if palindrome(sub):
						temp.append(sub)
						part(i + 1, s, temp, ans)
						temp.pop()
		ans = []
		part(0, s, [], ans)
		return ans


class Solution:

	def allPalindromicPerms(self, s):

		def func(ind, n, res, ans, s):
			if ind == n:
				res.append(ans.copy())
				return
			for i in range(ind, n):
				kk = s[ind:i + 1]
				if kk == kk[::-1]:
					ans.append(kk)
					func(i + 1, n, res, ans, s)
					ans.pop()
		ans = []
		res = []
		n = len(s)
		func(0, n, res, ans, s)
		return res


import collections

class Solution:

	def allPalindromicPerms(self, S):
		s = S
		dp = collections.defaultdict(str)
		ans = []
		for i in range(len(s)):
			dp[i, i] = s[i]
		for i in range(len(s) - 1, -1, -1):
			for j in range(i + 1, len(s)):
				if j - i == 1 and s[i] == s[j]:
					dp[i, j] = s[i] + s[j]
				elif (i + 1, j - 1) in dp and s[i] == s[j]:
					dp[i, j] = s[i] + dp[i + 1, j - 1] + s[j]

		def iterate(i, st):
			if i == len(s):
				ans.append(st)
			for j in range(i, len(s)):
				if (i, j) in dp:
					sx = st[:]
					sx.append(dp[i, j])
					iterate(j + 1, sx)
		iterate(0, [])
		return ans


class Solution:

	def allPalindromicPerms(self, s):
		res = []
		part = []

		def dfs(i):
			if i >= len(s):
				res.append(part[:])
				return
			for j in range(i, len(s)):
				if self.isPalin(s, i, j):
					part.append(s[i:j + 1])
					dfs(j + 1)
					part.pop()
			return res
		return dfs(0)

	def isPalin(self, s, i, j):
		if s[i:j + 1] == s[i:j + 1][::-1]:
			return True


class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		op = []

		def finding(start, end):
			if start == n:
				op.append(end)
				return
			for i in range(start, n):
				if S[start:i + 1] == S[start:i + 1][::-1]:
					finding(i + 1, end + [S[start:i + 1]])
		finding(0, [])
		return op


class Solution:

	def IsPalindrome(self, start, end, s):
		while start <= end:
			if s[start] != s[end]:
				return False
			start += 1
			end -= 1
		return True

	def helper(self, ind, n, s, ans, temp):
		if ind == n:
			ans.append(temp[:])
			return
		for i in range(ind, n):
			if self.IsPalindrome(ind, i, s):
				temp.append(s[ind:i + 1])
				self.helper(i + 1, n, s, ans, temp)
				temp.pop()

	def allPalindromicPerms(self, S):
		ans = []
		temp = []
		self.helper(0, len(S), S, ans, temp)
		return ans


class Solution:

	def allPalindromicPerms(self, S):

		def dfs(i, l):
			if i == len(S):
				ans.append(l[:])
				return
			for ind in range(i, len(S)):
				if S[i:ind + 1] == S[i:ind + 1][::-1]:
					l.append(S[i:ind + 1])
					dfs(ind + 1, l)
					l.pop()
		ans = []
		dfs(0, [])
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		import copy
		ans = []

		def f(index, p):
			if index == len(S):
				ans.append(copy.deepcopy(p))
				return
			for i in range(index, len(S)):
				t = S[index:i + 1]
				if t == t[::-1]:
					p.append(t)
					f(i + 1, p)
					p.pop()
		f(0, [])
		return ans


from copy import copy

class Solution:

	def allPalindromicPerms(self, S):
		lst = []
		res = []
		self.helper(0, S, lst, res)
		return res

	def checkpalindrome(self, a, b, s):
		while a <= b:
			if s[a] != s[b]:
				return False
			a += 1
			b -= 1
		return True

	def helper(self, idx, s, lst, res):
		if idx == len(s):
			res.append(copy(lst))
			return
		for i in range(idx, len(s)):
			if self.checkpalindrome(idx, i, s) == True:
				lst.append(s[idx:i + 1])
				self.helper(i + 1, s, lst, res)
				lst.pop()


class Solution:

	def allPalindromicPerms(self, s):
		l = []

		def dfs(x, n, a):
			if x is '':
				l.append(a[:])
				return
			y = ''
			for i in range(n):
				y += x[i]
				if y != y[::-1]:
					continue
				a.append(y)
				dfs(x[i + 1:], n - i - 1, a)
				a.pop(-1)
		dfs(s, len(s), [])
		return l


class Solution:

	def allPalindromicPerms(self, s):
		m = len(s)
		r = []
		a = []

		def check(string, i, j):
			x = j
			for y in range(i, x):
				if string[y] != string[x]:
					return False
				x -= 1
			return True

		def allPalPartUtil(allPart: list, currPart: list, start: int, n: int, string: str):
			if start >= n:
				x = currPart.copy()
				allPart.append(x)
				return
			for i in range(start, n):
				if check(string, start, i):
					currPart.append(string[start:i + 1])
					allPalPartUtil(allPart, currPart, i + 1, n, string)
					currPart.pop()
		allPalPartUtil(r, a, 0, m, s)
		return r


from collections import defaultdict

class Solution:

	def allPalindromicPerms(self, s):
		h = defaultdict(set)
		ans = []
		cans = []
		n = len(s)
		for i in range(n):
			p = q = i
			h[p].add(q)
			while p - 1 >= 0 and q + 1 < n and (s[p - 1] == s[q + 1]):
				p -= 1
				q += 1
				h[p].add(q)
		for i in range(n - 1):
			(p, q) = (i + 1, i)
			while p - 1 >= 0 and q + 1 < n and (s[p - 1] == s[q + 1]):
				p -= 1
				q += 1
				h[p].add(q)

		def rec(i, start):
			if i == n:
				if start == n:
					ans.append(cans[:])
				return
			if i in h[start]:
				cans.append(s[start:i + 1])
				rec(i + 1, i + 1)
				cans.pop()
			if len(h[start]) > 1:
				rec(i + 1, start)
		rec(0, 0)
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		res = []
		part = []

		def dfs(i):
			if i >= len(S):
				res.append(part.copy())
				return
			for j in range(i, len(S)):
				if self.isPalindrome(S, i, j):
					part.append(S[i:j + 1])
					dfs(j + 1)
					part.pop()
		dfs(0)
		return res

	def isPalindrome(self, S, l, r):
		while l <= r:
			if S[l] != S[r]:
				return False
			(l, r) = (l + 1, r - 1)
		return True


class Solution:

	def allPalindromicPerms(self, S):

		def go(ind):
			if ind == len(S):
				ans.append(p[:])
				return
			for i in range(ind, len(S)):
				if isP(S[ind:i + 1]):
					p.append(S[ind:i + 1])
					go(i + 1)
					p.pop(-1)

		def isP(x):
			l = 0
			r = len(x) - 1
			while l < r:
				if x[l] != x[r]:
					return False
				l += 1
				r -= 1
			return True
		p = []
		ans = []
		go(0)
		return ans


class Solution:

	def is_palindrome(self, string):
		j = len(string) - 1
		i = 0
		while i < j:
			if string[i] != string[j]:
				return False
			i += 1
			j -= 1
		return True

	def partition(self, string, ans, res):
		if len(string) == 0:
			res.add(' '.join(ans))
			return
		for i in range(len(string)):
			if self.is_palindrome(string[:i + 1]):
				self.partition(string[i + 1:], ans + [string[:i + 1]], res)

	def allPalindromicPerms(self, S):
		res = set()
		self.partition(S, [], res)
		res = [[x] for x in res]
		res = sorted(res)
		return res


class Solution:

	def allPalindromicPerms(self, S):
		n = len(S)
		result = []

		def sub(start, out):
			if start == n:
				result.append(out)
				return
			for i in range(start, n):
				if S[start:i + 1] == S[start:i + 1][::-1]:
					sub(i + 1, out + [S[start:i + 1]])
		sub(0, [])
		return result


class Solution:

	def isPalindrome(self, s):
		i = 0
		j = len(s) - 1
		while i < j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True

	def backtrack(self, i, n, temp, l, S):
		if i >= n:
			l.append(temp[:])
		p = ''
		for j in range(i, n):
			p += S[j]
			if self.isPalindrome(p):
				temp.append(p)
				self.backtrack(j + 1, n, temp, l, S)
				temp.pop()

	def allPalindromicPerms(self, S):
		l = []
		self.backtrack(0, len(S), [], l, S)
		return l


class Solution:

	def allPalindromicPerms(self, S):
		ans = []
		a = []
		n = len(S)

		def check(s):
			return s == s[::-1]

		def sol(i, n):
			if i == n:
				ans.append(a.copy())
				return
			for j in range(n - i):
				if check(S[i:i + j + 1]):
					a.append(S[i:i + j + 1])
					sol(i + j + 1, n)
					a.pop()
		sol(0, n)
		return ans


class Solution:

	def is_palindrome(self, S):
		low = 0
		high = len(S) - 1
		while low < high:
			if S[low] != S[high]:
				return False
			low += 1
			high -= 1
		return True

	def solve(self, S, part, res):
		for i in range(len(S)):
			prefix = S[:i + 1]
			if self.is_palindrome(prefix):
				rest = S[i + 1:]
				if len(rest) == 0:
					part.append(prefix)
					res.append(part[:])
					part.pop()
					return
				part.append(prefix)
				self.solve(rest, part, res)
				part.pop()

	def allPalindromicPerms(self, S):
		res = []
		self.solve(S, [], res)
		return res


class Solution:

	def is_palindrome(self, start, end, nums):
		while start <= end:
			if nums[start] != nums[end]:
				return False
			start = start + 1
			end = end - 1
		return True

	def helper(self, ind, nums, path, ans):
		if ind == len(nums):
			ans.append(list(path))
			return
		for i in range(ind, len(nums)):
			if self.is_palindrome(ind, i, nums):
				path.append(''.join(nums[ind:i + 1]))
				self.helper(i + 1, nums, path, ans)
				path.pop()

	def allPalindromicPerms(self, S):
		ans = []
		self.helper(0, list(S), [], ans)
		return ans


class Solution:

	def allPalindromicPerms(self, S):
		t = len(S)
		rest = []

		def subt(first, last):
			if first == t:
				rest.append(last)
				return
			for i in range(first, t):
				if S[first:i + 1] == S[first:i + 1][::-1]:
					subt(i + 1, last + [S[first:i + 1]])
		subt(0, [])
		return rest


class Solution:

	def allPalindromicPerms(self, s):
		l = []

		def backtrack(a, s):
			if s is '':
				l.append(a[:])
				return
			n = len(s)
			x = ''
			for i in range(n):
				x += s[i]
				if x == x[::-1]:
					a.append(x)
					backtrack(a, s[i + 1:])
					a.pop(-1)
		backtrack([], s)
		return l


class Solution:

	def isPali(self, str):
		i = 0
		j = len(str) - 1
		while i < j:
			if str[i] != str[j]:
				return False
			i += 1
			j -= 1
		return True

	def solve(self, str):
		if len(str) == 1:
			return [[str[0]]]
		curr = []
		for i in range(1, len(str)):
			if not self.isPali(str[:i]):
				continue
			prev = self.solve(str[i:])
			for p in prev:
				p.insert(0, str[:i])
				curr.append(p)
		if self.isPali(str):
			curr.append([str])
		return curr

	def allPalindromicPerms(self, str):
		return self.solve(str)


class Solution:

	def allPalindromicPerms(self, S):
		ans = []
		part = []

		def dfs(i=0):
			if i == len(S):
				ans.append(part[:])
				return
			for j in range(i, len(S)):
				if self.checkPal(S, i, j):
					part.append(S[i:j + 1])
					dfs(j + 1)
					part.pop()
		dfs()
		return ans

	def checkPal(self, S, i, j):
		while i < j:
			if S[i] != S[j]:
				return False
			i += 1
			j -= 1
		return True


class Solution:

	def allPalindromicPerms(self, S):
		ans = []
		part = []

		def dfs(i=0):
			if i == len(S):
				ans.append(part[:])
				return
			for j in range(i, len(S)):
				if self.checkPal(S[i:j + 1]):
					part.append(S[i:j + 1])
					dfs(j + 1)
					part.pop()
		dfs()
		return ans

	def checkPal(self, str):
		return str == str[::-1]


class Solution:

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

		def rec(idx, path, res):
			if idx == len(s):
				res.append(path[:])
				return
			for i in range(idx, len(s)):
				if ispali(s, idx, i):
					path.append(s[idx:i + 1])
					rec(i + 1, path, res)
					path.pop(-1)

		def ispali(s, left, right):
			while left <= right:
				if s[left] != s[right]:
					return False
				left += 1
				right -= 1
			return True
		rec(0, [], res)
		return res


class Solution:

	def ispal(self, s):
		if s == s[::-1]:
			return True
		return False

	def helper(self, allpart, curpart, start, end, s):
		if start >= end:
			x = curpart.copy()
			allpart.append(x)
			return
		for i in range(start, end):
			if self.ispal(s[start:i + 1]):
				curpart.append(s[start:i + 1])
				self.helper(allpart, curpart, i + 1, end, s)
				curpart.pop()
		return allpart

	def allPalindromicPerms(self, S):
		ans = self.helper([], [], 0, len(S), S)
		return ans