Given a string S. The task is to print all unique permutations of the given string in lexicographically sorted order.
Example 1:
Input: ABC
Output:
ABC ACB BAC BCA CAB CBA
Explanation:
Given string ABC has permutations in 6 
forms as ABC, ACB, BAC, BCA, CAB and CBA .
Example 2:
Input: ABSG
Output:
ABGS ABSG AGBS AGSB ASBG ASGB BAGS 
BASG BGAS BGSA BSAG BSGA GABS GASB 
GBAS GBSA GSAB GSBA SABG SAGB SBAG 
SBGA SGAB SGBA
Explanation:
Given string ABSG has 24 permutations.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function find_permutaion() which takes the string S as input parameter and returns a vector of string in lexicographical order.
Expected Time Complexity: O(n! * n)
Expected Space Complexity: O(n! * n)
Constraints:
1 <= length of string <= 5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def find_permutation(self, S):

        # Code here

        



Solutions:
from itertools import permutations

class Solution:

	def find_permutation(self, S):
		lst = []
		all_pm = permutations(S)
		for pm in all_pm:
			lst.append(''.join(pm))
		return sorted(list(set(lst)))


class Solution:

	def solve(self, ans, nums, i):
		if i == len(nums):
			if ''.join(nums[:]) not in ans:
				ans.append(''.join(nums[:]))
			return
		for j in range(i, len(nums)):
			(nums[i], nums[j]) = (nums[j], nums[i])
			self.solve(ans, nums, i + 1)
			(nums[i], nums[j]) = (nums[j], nums[i])

	def find_permutation(self, S):
		ans = []
		nums = list(S)
		self.solve(ans, nums, 0)
		ans = sorted(ans)
		return ans


res = []

def pl(s):
	global res
	r = ''
	for i in s:
		r += i
	res += [r]

def swap(l, a, b):
	t = l[a]
	l[a] = l[b]
	l[b] = t

def perm(s, l, r):
	if l == r:
		pl(s)
	else:
		for i in range(l, r + 1):
			swap(s, l, i)
			perm(s, l + 1, r)
			swap(s, l, i)

class Solution:

	def find_permutation(self, s):
		r = []
		global res
		perm(list(s), 0, len(s) - 1)
		res.sort()
		for i in res:
			if i not in r:
				r += [i]
		res = []
		return r


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		l = []
		for i in permutations(S):
			if ''.join(i) not in l:
				l.append(''.join(i))
		return sorted(l)


class Solution:

	def find_permutation(self, S):
		k = []
		l = 0
		r = len(S)
		S = list(S)

		def find(S, l, r, k):
			if l == r:
				k.append(''.join(S))
			else:
				for i in range(l, r):
					(S[l], S[i]) = (S[i], S[l])
					find(S, l + 1, r, k)
					(S[i], S[l]) = (S[l], S[i])
		find(S, l, r, k)
		k = set(k)
		k = list(k)
		k.sort()
		return k


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		l = []
		li = permutations(S)
		for i in li:
			l.append(''.join(i))
		l = set(l)
		l = list(l)
		l.sort()
		return l


class Solution:

	def find_permutation(self, s):
		list1 = []

		def dfs(s, temp, list1):
			if len(s) == 0:
				if temp not in list1:
					list1.append(temp)
				return
			for i in range(len(s)):
				dfs(s[:i] + s[i + 1:], temp + s[i], list1)
		dfs(s, '', list1)
		return sorted(list1)


class Solution:

	def find_permutation(self, S):
		op = ''
		arr = []
		vector = [False] * len(S)
		self.solve(arr, op, vector, S)
		arr.sort()
		return arr

	def solve(self, arr, op, vector, s):
		if len(op) == len(s):
			if op not in arr:
				arr.append(op)
			return
		for i in range(len(s)):
			if vector[i] == False:
				vector[i] = True
				op += s[i]
				self.solve(arr, op, vector, s)
				op = op.replace(op[-1], '')
				vector[i] = False


class Solution:

	def permute(self, s, temp, ans):
		if len(s) == 0:
			ans.append(temp)
			return
		for (i, char) in enumerate(s):
			if i > 0 and char == s[i - 1]:
				continue
			temp += char
			self.permute(s[:i] + s[i + 1:], temp, ans)
			temp = temp[:-1]

	def find_permutation(self, s):
		ans = []
		self.permute(sorted(s), '', ans)
		return ans


class Solution:

	def find_permutation(self, string):
		chars = list(string)
		chars.sort()
		permutations = []
		visited = [False] * len(chars)
		self.backtrack(chars, visited, [], permutations)
		return permutations

	def backtrack(self, chars, visited, current, permutations):
		if len(current) == len(chars):
			permutations.append(''.join(current))
			return
		for i in range(len(chars)):
			if visited[i] or (i > 0 and chars[i] == chars[i - 1] and (not visited[i - 1])):
				continue
			visited[i] = True
			current.append(chars[i])
			self.backtrack(chars, visited, current, permutations)
			current.pop()
			visited[i] = False


from collections import Counter

class Solution:

	def find_permutation(self, S):
		ans = []
		res = []
		n = len(S)
		S = sorted(list(S))
		countr = Counter(S)

		def bts(i, countr):
			if len(ans) == n:
				res.append(''.join(ans[:]))
				return res
			for i in range(n):
				if i > 0 and S[i] == S[i - 1]:
					continue
				if countr[S[i]] > 0:
					ans.append(S[i])
					countr[S[i]] -= 1
					bts(i + 1, countr)
					ans.pop()
					countr[S[i]] += 1
		bts(0, countr)
		return res


class Solution:

	def find_permutation(self, S):
		if len(S) == 1:
			return [S[0]]
		ch = S[0]
		ss = S[1:]
		rr = self.find_permutation(ss)
		mr = []
		for ele in rr:
			for i in range(len(ele) + 1):
				mr.append(ele[0:i] + ch + ele[i:])
		my_list = list(set(mr))
		sorted_list = sorted(my_list, key=lambda x: x[:2])
		return sorted_list


class Solution:

	def find_permutation(self, s):
		result = []
		list_s = sorted(list(s))
		permutation(list_s, 0, result)
		return sorted(result)

def permutation(s, index, result):
	if index == len(s):
		result.append(''.join(s[:]))
		return
	for i in range(index, len(s)):
		if i != index and s[i] == s[i - 1]:
			continue
		(s[i], s[index]) = (s[index], s[i])
		permutation(s, index + 1, result)
		(s[i], s[index]) = (s[index], s[i])


class Solution:

	def find_permutation(self, S):
		n = len(S)

		def solve(ind, ds, vis):
			ds.append(S[ind])
			vis[ind] = 1
			if len(ds) == n:
				perm.append(''.join(ds))
			for c in range(len(vis)):
				if vis[c] == 0:
					solve(c, ds, vis)
			vis[ind] = 0
			ds.pop()
		vis = [0] * n
		ds = []
		perm = []
		for i in range(n):
			solve(i, ds, vis)
		perm = list(set(perm))
		perm.sort()
		return perm


class Solution:

	def find_permutation(self, S):

		def solve(arr, ans, idx):
			if idx == len(arr):
				if ''.join(arr) not in ans:
					ans.append(''.join(arr))
			for i in range(idx, len(arr)):
				(arr[idx], arr[i]) = (arr[i], arr[idx])
				solve(arr, ans, idx + 1)
				(arr[idx], arr[i]) = (arr[i], arr[idx])
		ans = []
		arr = list(S)
		solve(arr, ans, 0)
		ans.sort()
		return ans


from itertools import permutations

class Solution:

	def find_permutation(self, s):
		p = permutations(s)
		l = []
		for i in p:
			r = ''
			for j in i:
				r += j
			l.append(r)
		l.sort()
		c = []
		m = []
		for i in l:
			if i not in c:
				c.append(i)
		return c


class Solution:

	def find_permutation(self, S):
		from itertools import permutations
		result = set(permutations(S))
		result = sorted([''.join(p) for p in result])
		return result


class Solution:

	def toString(self, List):
		return ''.join(List)

	def permute(self, a, l, r, words):
		if l == r:
			words.add(self.toString(a))
			return
		else:
			for i in range(l, r):
				(a[l], a[i]) = (a[i], a[l])
				self.permute(a, l + 1, r, words)
				(a[l], a[i]) = (a[i], a[l])

	def find_permutation(self, S):
		words = set()
		words2 = []
		n = len(S)
		a = list(S)
		self.permute(a, 0, n, words)
		for x in words:
			words2.append(x)
		words2.sort()
		return words2


class Solution:

	def find_permutation(self, S):
		self.ans = []
		S = list(S)

		def recursive(index):
			if index == len(S) - 1:
				temp = S[:]
				self.ans.append(''.join(temp))
				return
			uset = set()
			for i in range(index, len(S)):
				if S[i] not in uset:
					uset.add(S[i])
					(S[i], S[index]) = (S[index], S[i])
					recursive(index + 1)
					(S[i], S[index]) = (S[index], S[i])
		recursive(0)
		return sorted(self.ans)


class Solution:

	def find_permutation(self, S):

		def seq(S, ans, i):
			if len(S) == i:
				ans.append(''.join(S))
			for j in range(i, len(S)):
				(S[i], S[j]) = (S[j], S[i])
				seq(S, ans, i + 1)
				(S[i], S[j]) = (S[j], S[i])
		ans = []
		S = list(S)
		seq(S, ans, 0)
		ans = list(set(ans))
		ans.sort()
		return ans


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		data = list(set(permutations(S)))
		for i in range(len(data)):
			data[i] = ''.join(data[i])
		return sorted(data)


class Solution:

	def permutation(self, result, arr, start):
		if start == len(arr) - 1:
			s = ''.join(arr)
			result.append(s)
			return
		for i in range(start, len(S)):
			(arr[start], arr[i]) = (arr[i], arr[start])
			self.permutation(result, arr, start + 1)
			(arr[start], arr[i]) = (arr[i], arr[start])
		return

	def find_permutation(self, S):
		result = []
		arr = list(map(str, S))
		self.permutation(result, arr, 0)
		set_result = set(result)
		f_result = list(set_result)
		f_result.sort()
		return f_result


class Solution:

	def find_permutation(self, S):
		perm_set = set()

		def generate_permutations(s, l, r):
			if l == r:
				perm_set.add(s)
			else:
				for i in range(l, r + 1):
					s_list = list(s)
					(s_list[l], s_list[i]) = (s_list[i], s_list[l])
					s_new = ''.join(s_list)
					generate_permutations(s_new, l + 1, r)
					(s_list[l], s_list[i]) = (s_list[i], s_list[l])
		generate_permutations(S, 0, len(S) - 1)
		perm_list = sorted(list(perm_set))
		return perm_list


class Solution:

	def find_permutation(self, S):
		result = set()

		def helper(string, slate):
			if not string:
				result.add(slate)
				return
			for i in range(len(string)):
				helper(string[:i] + string[i + 1:], slate + string[i])
		helper(S, '')
		return list(sorted(result))


class Solution:

	def toString(self, List):
		return ''.join(List)

	def backtracking(self, arr, l, r, vec):
		if l == r:
			if self.toString(arr) not in vec:
				vec.append(self.toString(arr))
		else:
			for i in range(l, r):
				(arr[l], arr[i]) = (arr[i], arr[l])
				self.backtracking(arr, l + 1, r, vec)
				(arr[l], arr[i]) = (arr[i], arr[l])
		return True

	def find_permutation(self, S):
		n = len(S)
		arr = list(S)
		vec = []
		self.backtracking(arr, 0, n, vec)
		return sorted(vec)


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		lst = []
		for i in permutations(S):
			lst.append(''.join(i))
		return sorted(set(lst))


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		res = permutations(S)
		ans = set()
		for i in res:
			temp = ''
			for j in i:
				temp += j
			ans.add(temp)
		return sorted(ans)


class Solution:

	def ansd(self, i, S, ans):
		con = len(S)
		if i >= con:
			if S not in ans:
				ans.append(S)
			return ans
		else:
			st = i
			while st < con:
				os = S
				if st != i:
					temp1 = os[i]
					temp2 = os[st]
					swaped = os[:i] + temp2 + os[i + 1:st] + temp1 + os[st + 1:]
					self.ansd(i + 1, swaped, ans)
				else:
					self.ansd(i + 1, S, ans)
				st = st + 1
		return ans

	def find_permutation(self, S):
		k = []
		ans = self.ansd(0, S, k)
		ans.sort()
		return ans


class Solution:

	def find_permutation(self, S):

		def Permutaion(ip, op):
			if len(ip) == 0:
				if op not in self.ans:
					self.ans.append(op)
				return
			for i in range(len(ip)):
				req_ip = ip[:i] + ip[i + 1:]
				Permutaion(req_ip, op + ip[i])
		self.ans = []
		Permutaion(S, '')
		return sorted(self.ans)


import itertools

class Solution:

	def find_permutation(self, S):
		permutations = itertools.permutations(S)
		return sorted(list(dict.fromkeys(list((''.join(i) for i in list(permutations))))))


class Solution:

	def __init__(self):
		self.ans = []

	def find(self, s, i):
		if i == len(s):
			self.ans.append(s)
		else:
			for j in range(i, len(s), 1):
				l = []
				for k in s:
					l.append(k)
				temp = l[j]
				l[j] = l[i]
				l[i] = temp
				self.find(''.join(l), i + 1)

	def find_permutation(self, S):
		self.find(S, 0)
		return sorted(list(set(self.ans)))


class Solution:

	def find_permutation(self, S):
		S = list(S)
		res = set()
		perm = []
		used = [False for i in range(len(S))]

		def backtrack():
			if len(perm) == len(S):
				res.add(''.join(perm))
				return
			for i in range(len(used)):
				if used[i]:
					continue
				used[i] = True
				perm.append(S[i])
				backtrack()
				used[i] = False
				perm.pop()
		backtrack()
		return sorted(list(res))


class Solution:

	def find_permutation(self, S):
		import itertools as it
		x = list(it.permutations(S))
		a = []
		for i in x:
			if ''.join(i) not in a:
				a.append(''.join(i))
		s = sorted(a)
		return s


import itertools

class Solution:

	def find_permutation(self, S):
		a = set()
		p = itertools.permutations(S, len(S))
		for i in p:
			a.add(''.join(i))
		a = sorted(a)
		return a


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		a = [''.join(i) for i in list(permutations(S))]
		b = []
		for i in a:
			if i not in b:
				b.append(i)
		b = sorted(b)
		return b


class Solution:

	def find_permutation(self, S):
		if len(S) == 0:
			arr = []
			arr.append('')
			return arr
		output = []
		for i in range(len(S)):
			smallOut = self.find_permutation(S[0:i] + S[i + 1:])
			for j in smallOut:
				output.append(S[i] + j)
		output2 = []
		for i in output:
			if i in output2:
				pass
			else:
				output2.append(i)
		return sorted(output2)


class Solution:

	def find_permutation(self, S):
		result = []

		def generate_permutations(current_permutation, used):
			if len(current_permutation) == len(S):
				result.append(current_permutation)
				return
			for i in range(len(S)):
				if used[i]:
					continue
				if i > 0 and S[i] == S[i - 1] and (not used[i - 1]):
					continue
				used[i] = True
				generate_permutations(current_permutation + S[i], used)
				used[i] = False
		S = ''.join(sorted(S))
		generate_permutations('', [False] * len(S))
		return result


class Solution:

	def find_permutation(self, S):
		i = 0
		res = []
		arr = [i for i in S]
		self.func(i, res, arr)
		f_ans = list(set(res))
		f_ans.sort()
		return f_ans

	def func(self, i, res, arr):
		if i == len(arr) - 1:
			res.append(''.join(arr))
			return
		for j in range(i, len(arr)):
			(arr[i], arr[j]) = (arr[j], arr[i])
			self.func(i + 1, res, arr)
			(arr[i], arr[j]) = (arr[j], arr[i])


class Solution:

	def helper(self, s, l, h, res):
		if l == h:
			res.append(''.join(s))
			return
		for i in range(l, h):
			(s[i], s[l]) = (s[l], s[i])
			self.helper(s, l + 1, h, res)
			(s[l], s[i]) = (s[i], s[l])

	def find_permutation(self, S):
		res = []
		self.helper(list(S), 0, len(S), res)
		res = list(set(res))
		res.sort()
		return res


import itertools

class Solution:

	def find_permutation(self, S):
		return sorted(set([''.join(each) for each in itertools.permutations(S)]))
		ans = []
		S = list(S)
		if len(S) == 1:
			return S
		for i in range(len(S)):
			temp = S[i]
			remaining = S[:i] + S[i + 1:]
			perms = self.find_permutation(remaining)
			for each in perms:
				ans.append(temp + each)
		return sorted(set(ans))


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		l = []
		permlist = permutations(S)
		for perm in permlist:
			l.append(''.join(perm))
		l = set(l)
		l = list(l)
		l.sort()
		return l


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		premList = permutations(S)
		l = set()
		for prem in list(premList):
			l.add(''.join(prem))
		l = list(l)
		l.sort()
		return l


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		permList = permutations(S)
		d = set()
		for perm in list(permList):
			d.add(''.join(perm))
		d = list(d)
		d.sort()
		return d


class Solution:

	def find_permutation(self, S):
		S = list(S)
		S.sort()
		ans = []

		def solve(temp, s):
			if len(temp) == len(S):
				if ''.join(temp) not in ans:
					ans.append(''.join(temp))
				return
			for i in range(len(s)):
				temp.append(s[i])
				solve(temp, s[:i] + s[i + 1:])
				temp.pop()
		solve([], S)
		return ans


class Solution:

	def find_permutation(self, S):

		def backtrack(start):
			if start == len(S) - 1:
				permutations.add(''.join(S))
				return
			for i in range(start, len(S)):
				(S[start], S[i]) = (S[i], S[start])
				backtrack(start + 1)
				(S[start], S[i]) = (S[i], S[start])
		S = list(S)
		permutations = set()
		backtrack(0)
		permutations = sorted(list(permutations))
		return permutations


import itertools

class Solution:

	def find_permutation(self, S):
		l = []
		perms = set(itertools.permutations(S))
		sorted_perms = sorted(perms)
		for perm in sorted_perms:
			s = ''.join(perm)
			l.append(s)
		return l


class Solution:

	def find_permutation(self, s):
		n = len(s)
		perms = set()

		def permute(start, s_list):
			if start == n:
				perms.add(''.join(s_list))
				return
			for i in range(start, n):
				(s_list[start], s_list[i]) = (s_list[i], s_list[start])
				permute(start + 1, s_list)
				(s_list[start], s_list[i]) = (s_list[i], s_list[start])
		s_list = list(s)
		permute(0, s_list)
		result = list(perms)
		result.sort()
		return result


import itertools

class Solution:

	def find_permutation(self, S):
		S = sorted(S)
		unq_perm = []
		permutations = list(itertools.permutations(S))
		permutations = [''.join(i) for i in permutations]
		for i in permutations:
			if i not in unq_perm:
				unq_perm.append(i)
		return unq_perm


class Solution:

	def solve(self, data, start, ans):
		if start >= len(data):
			ans.add(''.join(data))
			return
		for idx in range(start, len(data)):
			(data[start], data[idx]) = (data[idx], data[start])
			self.solve(data, start + 1, ans)
			(data[start], data[idx]) = (data[idx], data[start])

	def find_permutation(self, S):
		ans = set()
		data = list(S)
		self.solve(data, 0, ans)
		ans = list(ans)
		ans.sort()
		return ans


import itertools

class Solution:

	def find_permutation(self, S):
		ans = []
		x = list(itertools.permutations(S, len(S)))
		for i in x:
			temp = ''
			for j in range(0, len(i)):
				temp += i[j]
			ans.append(temp)
		final_ans = set(ans)
		sorted_ans = list(final_ans)
		sorted_ans.sort()
		return sorted_ans


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		a = []
		permut = permutations(S)
		for perm in permut:
			a.append(''.join(perm))
		a = list(set(a))
		a.sort()
		return a


class Solution:

	def permute(self, S, ans, ls):
		if len(S) == 0 and ans not in ls:
			ls.append(ans)
			return
		for i in range(len(S)):
			ch = S[i]
			l = S[:i]
			r = S[i + 1:]
			res = l + r
			self.permute(res, ans + ch, ls)

	def find_permutation(self, S):
		ans = ''
		ls = []
		self.permute(S, ans, ls)
		return sorted(ls)


class Solution:

	def find_permutation(self, S):
		b = []
		from itertools import permutations
		perms = permutations(S)
		perms = sorted(perms)
		dic = {}
		for i in perms:
			x = ''.join(i)
			if x not in dic:
				b.append(x)
				dic[x] = 1
		return b


class Solution:

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

		def permutation(s, i):
			if i == len(s):
				if s not in res:
					res.append(s)
			elif s not in res:
				for j in range(0, len(s)):
					w = [w for w in s]
					(w[j], w[i]) = (w[i], w[j])
					word = ''.join(w)
					permutation(word, i + 1)
		permutation(s, 0)
		res.sort()
		return res


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		s = permutations(S)
		ans = []
		for i in s:
			l = ''
			for j in i:
				l = l + j
			ans.append(l)
		g = set(ans)
		h = list(g)
		h.sort()
		return h


class Solution:

	def find_permutation(self, S):

		def permute(arr, ds, ans, start):
			if len(arr) - 1 == start:
				ans.append(''.join(list(arr)))
				return
			for i in range(len(arr)):
				(arr[start], arr[i]) = (arr[i], arr[start])
				permute(arr, ds, ans, start + 1)
				(arr[i], arr[start]) = (arr[start], arr[i])
			return
		ans = []
		ds = []
		mp = {}
		arr = []
		for i in range(len(S)):
			arr.append(S[i])
		permute(arr, ds, ans, 0)
		ans = list(set(ans))
		ans = sorted(ans)
		return ans


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		res = []

		def permute(a, l, r):
			if l == r:
				k = ''.join(a)
				if k not in res:
					res.append(k)
			else:
				for i in range(l, r):
					(a[l], a[i]) = (a[i], a[l])
					permute(a, l + 1, r)
					(a[l], a[i]) = (a[i], a[l])
			return res
		p = [i for i in S]
		result = permute(p, 0, len(S))
		return sorted(result)


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		n = len(S)
		res = permutations(S)
		r = []
		for i in res:
			k = ''.join(i)
			if k not in r:
				r.append(k)
		return sorted(r)


class Solution:

	def find_permutation(self, S):

		def backtrack(first=0, curr=[]):
			if first == len(S):
				result.add(''.join(curr))
				return
			for i in range(first, len(S)):
				(S[i], S[first]) = (S[first], S[i])
				backtrack(first + 1, curr + [S[first]])
				(S[i], S[first]) = (S[first], S[i])
		result = set()
		S = [char for char in S]
		backtrack()
		return sorted(result)


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		P = permutations(S)
		Output = []
		for i in P:
			Ans = ''.join(i)
			Output.append(Ans)
		Output = list(set(Output))
		Output.sort()
		return Output


class Solution:

	def solve(self, s, ans, res):
		if len(s) == 0:
			if ans not in res:
				res.append(ans)
			return
		n = len(s)
		for i in range(n):
			ch = s[i]
			left = s[0:i]
			right = s[i + 1:]
			rest = left + right
			self.solve(rest, ans + ch, res)

	def find_permutation(self, S):
		res = []
		ans = ''
		self.solve(S, ans, res)
		res.sort()
		return res


class Solution:

	def solve(self, arr, ind, n, res):
		if ind == n:
			temp = ''.join(arr)
			if temp not in res:
				res.append(temp)
		for i in range(ind, n):
			(arr[i], arr[ind]) = (arr[ind], arr[i])
			self.solve(arr, ind + 1, n, res)
			(arr[i], arr[ind]) = (arr[ind], arr[i])

	def find_permutation(self, S):
		n = len(S)
		arr = list(S)
		res = []
		self.solve(arr, 0, n, res)
		res.sort()
		return res


class Solution:

	def find_permutation(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		res = []
		l = len(s)

		def sol(ind, str, d):
			if ind == l:
				res.append(str)
				return
			for i in d:
				if d[i] > 0:
					str += i
					d[i] -= 1
					sol(ind + 1, str, d)
					str = str[:-1]
					d[i] += 1
		sol(0, '', d)
		res = sorted(res)
		return res


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		perms = [''.join(p) for p in permutations(S)]
		for i in perms:
			if perms.count(i) > 1:
				perms.pop()
		return sorted(set(perms))


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		ans = list(permutations(S))
		ans.sort()
		res = []
		for i in ans:
			str = ''.join(i)
			if str not in res:
				res.append(str)
		return res


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		lst = []
		permute = permutations(S)
		for p in permute:
			lst.append(''.join(p))
		lst = set(lst)
		return sorted(list(lst))


from itertools import permutations

class Solution:

	def find_permutation(self, s):
		ans = permutations(s)
		ans = list(ans)
		l = []
		for i in ans:
			k = ''.join(i)
			l = l + [k]
		l = set(l)
		l = list(l)
		l.sort()
		return l


class Solution:

	def recur(self, S, index, res, path):
		if index == len(S):
			res.append(S[:])
			return
		else:
			for i in range(index, len(S)):
				(S[i], S[index]) = (S[index], S[i])
				self.recur(S, index + 1, res, path)
				(S[i], S[index]) = (S[index], S[i])

	def find_permutation(self, S):
		res = []
		path = []
		L = list(S)
		self.recur(L, 0, res, path)
		ans = []
		for i in res:
			ans.append(''.join(i))
		final = list(set(ans))
		final.sort()
		return final


class Solution:

	def permutation_rec(self, rest_letters):
		if len(rest_letters) == 1:
			return rest_letters[0]
		new_ends = []
		for i in range(len(rest_letters)):
			letter = rest_letters[i]
			new_rest_letters = rest_letters.copy()
			new_rest_letters.remove(letter)
			ends = self.permutation_rec(new_rest_letters)
			for end in ends:
				new_ends.append(letter + end)
		return new_ends

	def find_permutation(self, S):
		letters = []
		for i in range(len(S)):
			letters.append(S[i])
		permutations = self.permutation_rec(letters)
		unique_perm = []
		for perm in permutations:
			if perm not in unique_perm:
				unique_perm.append(perm)
		unique_perm.sort()
		return unique_perm


class Solution:

	def find_permutation(self, S):
		l = []
		a = []
		f = [0] * len(S)

		def x(s, l, a, f):
			if len(l) == len(s):
				y = ''.join(l)
				if y not in a:
					a.append(y)
				return
			for i in range(len(s)):
				if not f[i]:
					f[i] = 1
					l.append(s[i])
					x(s, l, a, f)
					f[i] = 0
					l.pop()
			a.sort()
			return a
		return x(S, l, a, f)


from itertools import permutations

class Solution:

	def find_permutation(self, S):
		p = list(permutations(S))
		l = []
		for i in p:
			s = ''
			for j in i:
				s += j
			if s not in l:
				l.append(s)
		return sorted(l)