# string permutation in lexicographically order with repetition of characters in the string

def permute(input):

count_map = {}

for ch in input:

if ch in count_map.keys():

count_map[ch] = count_map[ch] + 1

else:

count_map[ch] = 1

keys = sorted(count_map)

str = []

count = []

for key in keys:

str.append(key)

count.append(count_map[key])

result = [0 for x in range(len(input))]

permute_util(str, count, result, 0)

def permute_util(str, count, result, level):

if level == len(result):

print(result)

return

for i in range(len(str)):

if count[i] == 0:

continue;

result[level] = str[i]

count[i] -= 1

permute_util(str, count, result, level + 1)

count[i] += 1

if __name__ == '__main__':

input = ['B', 'C', 'A', 'A']

permute(input)