# Find all Lexicographic Permutations of a String

In this post, we will see how to find all lexicographic permutations of a string where repetition of characters is allowed.

For example, consider string ABC. It has following lexicographic permutations with repetition of characters –

AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB
BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC

We can use recursion to solve this problem. We start by sorting the string so that the characters are considered in lexicographical order. Then at any point in the recursion, the current index in the output string is filled with each character of the input string one by one and we recurse for the next index.

## Java

Output:

AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB
BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC

Above solution doesn’t handle duplicates in the output. For example, for string AAB it prints –

AAA AAA AAB AAA AAA AAB ABA ABA ABB AAA AAA AAB AAA AAA
AAB ABA ABA ABB BAA BAA BAB BAA BAA BAB BBA BBA BBB

Here, AAA is repeated 8 times, AAB, ABA, BAA is repeated 4 times and ABB, BAB, BBA is repeated 2 times. Below code efficiently handles duplicates in the output –

## Java

Output:

AAA AAB ABA ABB BAA BAB BBA BBB

(1 votes, average: 5.00 out of 5)