Given a string S. The task is to find all permutations of a given string.
Example 1:
Input:
S = ABC
Output: ABC ACB BAC BCA CAB CBA 
Example 2:
Input:
S = 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
 
Your Task:
This is a function problem. You only need to complete the function permutation that takes S as parameter and returns the list of permutations in lexicographically increasing order. The newline is automatically added by driver code.
Constraints:
1 ≤ size of string ≤ 5
Expected Time Complexity: O(N * N!), N = length of string.
Expected Auxiliary Space: O(1)

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:
    def permutation(self,s):
        

Solutions:
class Solution:

	def permutation(self, s):
		self.ans = []
		seen = set()
		s = sorted(s)

		def recursion(ds, seen):
			if len(ds) == len(s):
				self.ans.append(ds)
				return
			for i in range(len(s)):
				if s[i] not in seen:
					seen.add(s[i])
					recursion(ds + s[i], seen)
					seen.remove(s[i])
		recursion('', seen)
		return self.ans


class Solution:

	def permutation(self, s):
		n = len(s)
		if n == 1:
			return [s[0]]
		result = []
		for i in range(n):
			a = s[:i] + s[i + 1:]
			b = self.permutation(a)
			for j in b:
				result.append(s[i] + j)
		result.sort()
		return result


class Solution:

	def permutation(self, s):
		lst = [z for z in s]
		lst.sort()
		s = ''
		for y in lst:
			s += y

		def perm(s, ans, lst):
			if len(s) == 0:
				lst.append(ans)
				return
			for i in range(len(s)):
				ch = s[i]
				l = s[0:i]
				r = s[i + 1:]
				rem = l + r
				perm(rem, ans + ch, lst)
			return lst
		return perm(s, '', [])


from collections import Counter

class Solution:

	def 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 permutation(self, s):
		if len(s) == 1:
			return [s[0]]
		output = []
		for i in range(len(s)):
			remchar = s[:i] + s[i + 1:]
			permofrem = self.permutation(remchar)
			for ans in permofrem:
				output.append(s[i] + ans)
		output.sort()
		return output


from itertools import permutations

class Solution:

	def permutation(self, s):
		s = sorted(s)
		p = permutations(s, len(s))
		for i in p:
			for j in i:
				print(j, end='')
			print(end=' ')
		return []


class Solution:

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

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

	def permutation(self, s):
		self.find(s, 0)
		return sorted(self.ans)


from itertools import permutations

class Solution:

	def 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 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])


def per(s, i, n, b):
	if i == n:
		b.append(''.join(s))
	else:
		for j in range(i, n + 1):
			(s[i], s[j]) = (s[j], s[i])
			per(s, i + 1, n, b)
			(s[j], s[i]) = (s[i], s[j])
	return b

class Solution:

	def permutation(self, s):
		a = len(s) - 1
		b = []
		S = list(s)
		return sorted(list(set(per(S, 0, a, b))))


from itertools import permutations

class Solution:

	def permutation(self, s):
		s = sorted(s)
		perm = [''.join(i) for i in list(permutations(s))]
		return perm


class Solution:

	def permutation(self, s):
		p = ''
		ans = []
		self.helper(s, p, ans)
		ans.sort()
		return ans

	def helper(self, s, p, ans):
		if len(s) == 0:
			ans.append(p)
			return
		for i in range(0, len(s)):
			ch = s[i]
			f = s[0:i]
			l = s[i + 1:]
			rest = f + l
			self.helper(rest, p + ch, ans)


class Solution:

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

		def permute(string, answer):
			if len(string) == 0:
				list1.append(answer)
				return
			for i in range(len(string)):
				char = string[i]
				left_substring = string[0:i]
				right_substring = string[i + 1:]
				remaining_string = left_substring + right_substring
				permute(remaining_string, answer + char)
		answer = ''
		permute(s, answer)
		return sorted(list1)


class Solution:

	def 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 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 permutation(self, s):
		s = ''.join(sorted(s))
		P = permutations(s)
		out = []
		for i in P:
			Ans = ''.join(i)
			out.append(Ans)
		return out


class Solution:

	def permutation(self, s):

		def backtrack(start):
			if start == n:
				result.append(''.join(chars))
			for i in range(start, n):
				(chars[start], chars[i]) = (chars[i], chars[start])
				backtrack(start + 1)
				(chars[start], chars[i]) = (chars[i], chars[start])
		n = len(s)
		chars = list(s)
		result = []
		backtrack(0)
		result.sort()
		return result


def permut(s, i, lis):
	if i == len(s):
		z = ''.join(s)
		if z not in lis:
			lis.append(z)
			return
	else:
		for j in range(len(s)):
			(s[i], s[j]) = (s[j], s[i])
			permut(s, i + 1, lis)
			(s[i], s[j]) = (s[j], s[i])

class Solution:

	def permutation(self, s):
		s = list(s)
		i = 0
		lis = []
		permut(s, i, lis)
		lis.sort()
		return lis


class Solution:

	def permutation(self, s):
		if len(s) == 0:
			return ['']
		rv = []
		for first in s:
			for rest in self.permutation([x for x in s if x != first]):
				rv.append(first + rest)
		return sorted(rv)


from itertools import permutations as p

class Solution:

	def permutation(self, s):
		a = list(p(s))
		a.sort()
		b = []
		for i in a:
			x = ''
			x = ''.join(i)
			b.append(x)
		return b


class Solution:

	def permutation(self, s):
		result = []

		def helper(idx, arr, result):
			if idx == len(arr):
				temp = ''.join(arr)
				result.append(temp)
				return
			for i in range(idx, len(arr)):
				(arr[i], arr[idx]) = (arr[idx], arr[i])
				helper(idx + 1, arr, result)
				(arr[i], arr[idx]) = (arr[idx], arr[i])
		arr = list(map(str, s))
		helper(0, arr, result)
		result.sort()
		return result


class Solution:

	def permutation(self, s):
		import itertools
		s = sorted(s)
		s = ''.join(s)
		l = list(itertools.permutations(s, len(s)))
		l1 = []
		for i in range(len(l)):
			l1.append(''.join(l[i]))
		return l1


class Solution:

	def permutation(self, s):

		def helper(s, ind, res, n):
			if ind == n - 1:
				res.append(''.join(s))
				return
			for i in range(ind, n):
				(s[i], s[ind]) = (s[ind], s[i])
				helper(s, ind + 1, res, n)
				(s[i], s[ind]) = (s[ind], s[i])
		res = []
		s = list(s)
		helper(s, 0, res, len(s))
		res.sort()
		return res


from itertools import permutations

class Solution:

	def permutation(self, s):
		per = list(permutations(s))
		ans = list(map(lambda x: ''.join(x), per))
		ans.sort()
		return ans


class Solution:
	global a
	a = []

	def per(self, s, l, h):
		if l == h:
			a.append(''.join(s))
		else:
			for i in range(l, h):
				(s[i], s[l]) = (s[l], s[i])
				self.per(s, l + 1, h)
				(s[i], s[l]) = (s[l], s[i])

	def permutation(self, s):
		b = list(s)
		self.per(b, 0, len(b))
		c = list(a)
		a.clear()
		c.sort()
		return c


from itertools import permutations

class Solution:

	def permutation(self, s):
		t = []
		perm = permutations(s)
		for c in list(perm):
			t.append(''.join(c))
		t.sort()
		return t


class Solution:

	def permute(li, l, r, res):
		if l == r:
			res.append(''.join(li))
		else:
			for i in range(l, r + 1):
				(li[l], li[i]) = (li[i], li[l])
				Solution.permute(li, l + 1, r, res)
				(li[l], li[i]) = (li[i], li[l])

	def permutation(self, s):
		li = list(s)
		res = []
		Solution.permute(li, 0, len(li) - 1, res)
		res.sort()
		return res


from itertools import permutations

class Solution:

	def permutation(self, s):
		l = list(permutations(s, len(s)))
		l2 = []
		for i in sorted(l):
			l2.append(''.join(i))
		return l2


class Solution:

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

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

	def permutation(self, s):
		res = []
		a = list(s)
		n = len(s)
		self.permute(a, 0, n, res)
		res.sort()
		return res


from itertools import permutations

class Solution:

	def permutation(self, s):
		a = []
		p = permutations(s)
		for i in p:
			a.append(''.join(i))
		return sorted(set(a))


def backtracking(s):
	s = ''.join(sorted(s))
	times = {}
	for let in s:
		if let not in times:
			times[let] = 1
		else:
			times[let] += 1
	stack = []
	helper(len(s), times, '', stack)
	stack.sort()
	return stack

def helper(n, times, text, stack):
	if len(text) == n:
		stack.append(text)
	for let in times:
		if times[let]:
			times[let] -= 1
			helper(n, times, text + let, stack)
			times[let] += 1

class Solution:

	def permutation(self, s):
		return backtracking(s)


import itertools

class Solution:

	def permutation(self, S):
		per = set(itertools.permutations(S))
		li = []
		for i in per:
			li.append(''.join(i))
		li.sort()
		return li


import itertools

class Solution:

	def permutation(self, s):
		permutations = list(itertools.permutations(s))
		a = [''.join(i) for i in permutations]
		return sorted(a)


class Solution:

	def __init__(self):
		self.ans = set()

	def find_str(self, S, left, right):
		if left == right:
			self.ans.add(S)
		else:
			for i in range(left, right):
				S = self.swap(S, left, i)
				self.find_str(S, left + 1, right)
				S = self.swap(S, left, i)

	def swap(self, S, left, right):
		s_list = list(S)
		(s_list[left], s_list[right]) = (s_list[right], s_list[left])
		S = ''.join(s_list)
		return S

	def permutation(self, S):
		try:
			self.find_str(S, 0, len(S))
			return sorted(self.ans)
		except Exception as e:
			print('e', e)
			return []


class Solution:

	def per(self, s, li, t):
		if len(s) == 0:
			li.append(t)
			return
		for i in range(len(s)):
			t += s[i]
			self.per(s[:i] + s[i + 1:], li, t)
			t = t[:-1]

	def permutation(self, s):
		li = []
		s = list(s)
		s.sort()
		self.per(s, li, '')
		return li


class Solution:

	def permutation(self, s):

		def fun(s, l, i):
			if i == len(s) - 1:
				l.append(''.join(s))
				return
			for j in range(len(s)):
				re = [ele for ele in s]
				(re[i], re[j]) = (re[j], re[i])
				fun(re, l, i + 1)
			return
		l = []
		fun(s, l, 0)
		return sorted(set(l))


from itertools import permutations, combinations
import sys

class Solution:

	def permutation(self, s):
		res = permutations(s)
		l1 = []
		for r in res:
			str1 = ''
			for j in r:
				str1 += j
			l1.append(str1)
		l1.sort()
		return l1


from itertools import permutations

class Solution:

	def permutation(self, s):
		return sorted([''.join(item) for item in permutations(s)])


from itertools import permutations

class Solution:

	def permutation(self, s):
		b = permutations(s)
		l = []
		for i in b:
			l.append(''.join(i))
		l.sort()
		return l


class Solution:

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

	def permutation(self, s):
		arr = list(s)
		ans = []
		self.solve(arr, 0, [], ans)
		ans.sort()
		return ans


class Solution:

	def solve(self, ans, res, index):
		if index >= len(ans):
			S = ''
			for i in range(len(ans)):
				S = S + ans[i]
			res.append(S)
		for j in range(index, len(ans)):
			(ans[index], ans[j]) = (ans[j], ans[index])
			self.solve(ans, res, index + 1)
			(ans[index], ans[j]) = (ans[j], ans[index])

	def permutation(self, s):
		res = []
		index = 0
		ans = list(s)
		self.solve(ans, res, index)
		res.sort()
		return res


class Solution:

	def permutation(self, s):
		ans = []

		def pre(s, k):
			if len(s) == 0:
				ans.append(k)
				return
			for i in range(len(s)):
				ch = s[i]
				left = s[0:i]
				right = s[i + 1:len(s)]
				pre(left + right, k + ch)
		pre(s, '')
		ans.sort()
		return ans


class Solution:

	def fun(self, nums, ans, ds, maptab):
		if len(ds) == len(nums):
			ans.append(str(ds))
			return
		for i in range(len(nums)):
			if maptab[i] == 0:
				ds += nums[i]
				maptab[i] = 1
				self.fun(nums, ans, ds, maptab)
				maptab[i] = 0
				ds = ds[0:len(ds) - 1]

	def permutation(self, s):
		ans = list()
		ds = str()
		maptab = [0 for i in range(len(s))]
		self.fun(s, ans, ds, maptab)
		ans.sort()
		return ans


class Solution:

	def permutation(self, s):
		l = 0
		r = len(s)
		x = []
		sttr = list(s)
		self.permute(l, r, sttr, x)
		x.sort()
		return x

	def permute(self, l, r, sttr, x):
		if l == r:
			x.append(self.printt(sttr))
			return
		else:
			for i in range(l, r):
				(sttr[l], sttr[i]) = (sttr[i], sttr[l])
				self.permute(l + 1, r, sttr, x)
				(sttr[l], sttr[i]) = (sttr[i], sttr[l])

	def printt(self, sttr):
		return ''.join(sttr)


class Solution:

	def permutation(self, s):
		if len(s) == 0:
			arr = []
			arr.append('')
			return arr
		out = []
		for i in range(len(s)):
			smallOut = self.permutation(s[:i] + s[i + 1:])
			for j in smallOut:
				out.append(s[i] + j)
		return sorted(out)


class Solution:

	def permutation(self, s):
		import itertools as p
		x = p.permutations(s)
		x = list(x)
		x.sort()
		m = []
		a = ''
		for i in x:
			for j in i:
				a += ''.join(j)
			m.append(a)
			a = ''
		return m


class Solution:

	def permutation(self, S):
		a = list(S)
		r = len(S)
		result = []

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


class Solution:

	def permutation(self, string):
		res = []
		temp = ['']
		string = ''.join(sorted(string))

		def getPermutation(s):
			if not s:
				return
			if len(s) == 1:
				temp[0] += s
				res.append(temp[0])
				temp[0] = temp[0][:-1]
			for i in range(len(s)):
				temp[0] += s[i]
				getPermutation(s[:i] + s[i + 1:])
				temp[0] = temp[0][:-1]
		getPermutation(string)
		return res


class Solution:

	def permutation(self, s):
		ans = []
		n = len(s)
		ds = [i for i in s]

		def helper(ds, index):
			if index == n:
				ans.append(''.join(ds))
				return
			for j in range(index, n):
				(ds[index], ds[j]) = (ds[j], ds[index])
				helper(ds, index + 1)
				(ds[index], ds[j]) = (ds[j], ds[index])
		helper(ds, 0)
		ans.sort()
		return ans


class Solution:

	def permutation(self, s):
		ans = []
		n = len(s)
		ds = [False for i in range(n)]
		s = sorted(s)

		def helper(cs, ds, s):
			if len(cs) == n:
				ans.append(cs)
				return
			for i in range(0, n):
				if not ds[i]:
					ds[i] = True
					helper(cs + s[i], ds, s)
					ds[i] = False
		for i in range(0, n):
			ds[i] = True
			helper(s[i], ds, s)
			ds[i] = False
		return ans


from itertools import permutations

class Solution:

	def permutation(self, s):
		z = []
		for i in permutations(s):
			z.append(''.join(i))
		return sorted(z)


class Solution:

	def permutation(self, s):
		from itertools import permutations
		p = permutations(s)
		l = [''.join(pi) for pi in p]
		s = list(set(l))
		s.sort()
		return s


class Solution:

	def permutation(self, s):
		st = ''
		a = []
		freq = [0 for i in range(len(s))]

		def perm(a, st, s, freq):
			if len(st) == len(s):
				a.append(st)
				return
			for i in range(len(s)):
				if freq[i] == 0:
					st += s[i]
					freq[i] = 1
					perm(a, st, s, freq)
					freq[i] = 0
					st = st[:len(st) - 1]
		s = sorted(s)
		perm(a, st, s, freq)
		return a


class Solution:

	def permutation(self, S):
		a = []
		self.permute(S, 0, len(S) - 1, a)
		l = list(set(a))
		l.sort()
		return l

	def permute(self, S, l, r, a):
		if l == r:
			a.append(S)
			return a
		for i in range(l, r + 1):
			S = self.swap(S, l, i)
			self.permute(S, l + 1, r, a)
			S = self.swap(S, l, i)

	def swap(self, s, l, i):
		S = list(s)
		(S[l], S[i]) = (S[i], S[l])
		return ''.join(S)


class Solution:

	def permutation(self, s):
		if len(s) == 1:
			return [s]
		output = []
		for i in range(len(s)):
			rem = s[:i] + s[i + 1:]
			perm = self.permutation(rem)
			for ans in perm:
				output.append(s[i] + ans)
		output.sort()
		return output


import itertools

class Solution:

	def permutation(self, s):
		l = [''.join(i) for i in itertools.permutations(s)]
		l.sort()
		return l


class Solution:

	def permutation(self, s):
		ds = []
		s = list(s)
		n = len(s)

		def siva(ind):
			if ind >= n:
				ds.append(''.join(s))
				return
			for i in range(ind, n):
				(s[i], s[ind]) = (s[ind], s[i])
				siva(ind + 1)
				(s[ind], s[i]) = (s[i], s[ind])
		siva(0)
		return sorted(ds)


from itertools import permutations

class Solution:

	def permutation(self, s):
		p = permutations(s)
		out = []
		for i in p:
			if ''.join(i) not in out:
				out.append(''.join(i))
		return sorted(out)


class Solution:

	def permutation(self, s):
		from itertools import permutations
		ans = [''.join(i) for i in permutations(s)]
		ans.sort()
		return ans


from itertools import permutations

class Solution:

	def permutation(self, s):
		s = sorted(s)
		k = list(permutations(s))
		ans = []
		for i in k:
			ss = ''
			for j in i:
				ss += j
			ans.append(ss)
		return ans


class Solution:

	def slove(d, index, res):
		if index >= len(d):
			res.append(''.join(d))
			return
		for i in range(index, len(d)):
			(d[index], d[i]) = (d[i], d[index])
			Solution.slove(d, index + 1, res)
			(d[index], d[i]) = (d[i], d[index])

	def permutation(self, s):
		d = list(s)
		if len(s) == 0:
			return
		ans = ''
		res = []
		Solution.slove(d, 0, res)
		res.sort()
		return res


class Solution:

	def permutation(self, s):
		result = []
		lst = list(s)

		def perm(lst, i):
			if i == len(lst):
				string = ''.join(lst)
				result.append(string)
			else:
				for j in range(i, len(lst)):
					(lst[j], lst[i]) = (lst[i], lst[j])
					perm(lst, i + 1)
					(lst[j], lst[i]) = (lst[i], lst[j])
		perm(lst, 0)
		result.sort()
		return result


class Solution:

	def solve(self, s, start, end, ans):
		if start == end:
			ans.append(''.join(s))
			return
		for i in range(start, end):
			(s[start], s[i]) = (s[i], s[start])
			self.solve(s, start + 1, end, ans)
			(s[start], s[i]) = (s[i], s[start])

	def permutation(self, s):
		s = [i for i in s]
		ans = []
		self.solve(s, 0, len(s), ans)
		ans.sort()
		return ans


from itertools import permutations

class Solution:

	def permutation(self, s):
		x = []
		for i in permutations(s, len(s)):
			x.append(''.join(i))
		x.sort()
		return x


class Solution:

	def permutation(self, s):

		def permutations(word):
			if len(word) == 1:
				return [word]
			perms = permutations(word[1:])
			char = word[0]
			result = []
			for perm in perms:
				for i in range(len(perm) + 1):
					result.append(perm[i:] + char + perm[:i])
			return sorted(result)
		x = permutations(s)
		return x


import itertools

class Solution:

	def permutation(self, s):
		s = sorted(s)
		c = itertools.permutations(s)
		for i in c:
			s = ''
			for j in i:
				s += j
			print(s, end=' ')
		return ''


class Solution:

	def permutation(self, s):
		ans = []
		start = 0
		char_arr = [char for char in s]
		self.permUtil(char_arr, start, ans)
		ans.sort()
		return ans

	def permUtil(self, s, start, ans):
		if start == len(s) - 1:
			ans.append(''.join(s))
			return
		for i in range(start, len(s)):
			char_arr = [char for char in s]
			(char_arr[start], char_arr[i]) = (char_arr[i], char_arr[start])
			self.permUtil(char_arr, start + 1, ans)


class Solution:

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

	def helper(self, a, res, l, r):
		if l == r:
			res.append(self.toString(a))
		else:
			for i in range(l, r):
				(a[l], a[i]) = (a[i], a[l])
				self.helper(a, res, l + 1, r)
				(a[l], a[i]) = (a[i], a[l])

	def permutation(self, s):
		res = []
		a = list(s)
		n = len(s)
		self.helper(a, res, 0, n)
		return sorted(res)


from itertools import permutations

class Solution:

	def permutation(self, S):
		s = permutations(S, len(S))
		k = set(s)
		c = sorted(k)
		return [''.join(i) for i in c]


class Solution:

	def permutation(self, s):
		if len(s) == 1:
			return [s]
		permutations = Solution.permutation(self, s[1:])
		char = s[0]
		ans = []
		for permut in permutations:
			for i in range(len(permut) + 1):
				ans.append(permut[:i] + char + permut[i:])
		ans.sort()
		return ans


from itertools import permutations as p

class Solution:

	def permutation(self, s):
		ans = []
		permu = p(s)
		for i in permu:
			i = ''.join(i)
			ans.append(i)
		return sorted(ans)