# Permutations with duplicates

Before I start, I have to apologize for bringing up another case of permutations with duplicates. I have gone through most of the search results and can’t really find what I am looking for. I have read about the Lexicographical order and have implemented it. For this question, I am suppose to implement a recursion method that prints out the all the strings of length n consisting of just the characters a and b that have an equal number of a and b’s. The strings must be printed out one line at a time in lexical order. So, for example, a call:

```printBalanced(4);
```

will print the strings:

```aabb
abab
abba
baab
baba
bbaa
```

here is the code

```public static void main(String[] args){
printBalanced(4);
}

public static void printBalanced(int n){
String letters = "";

//string to be duplicates of "ab" depending the number of times the user wants it
for(int i =0; i<n/2;i++){
letters += "ab";
}

balanced("",letters);

}

private static void balanced(String prefix, String s){

int len = s.length();

//base case
if (len ==0){
System.out.println(prefix);
}
else{
for(int i = 0; i<len; i++){

balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));

}

}
}
```

My print results:

```abab
abba
aabb
aabb
abba
abab
baab
baba
baab
baba
bbaa
bbaa
aabb
aabb
abab
abba
abab
abba
baba
baab
bbaa
bbaa
baab
baba
```

As you can see, I get a lot of duplicates. This is partly due to the requirement to use only characters ‘a’ and ‘b’. The duplicates will not happen if it was “abcd” or “0123”. I have read about using an arraylist and store all the results and then loop through N elements to check for duplicates and then removing it. This does not seem to be the best way to do it. Can someone share about other better solutions for this problem? =)

My Solution using SortedSet:

```import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;

public class BalancedStrings {

public static void main(String[] args){

printBalanced(4);
}

public static void printBalanced(int n){
String letters = "";

for(int i =0; i<n/2;i++){
letters += "ab";
}

SortedSet<String> results = balanced("",letters);
Iterator<String> it = results.iterator();
while (it.hasNext()) {

// Get element and print
Object element = it.next();
System.out.println(element);
}

}

//This method returns a SortedSet with permutation results. SortedSet was chosen for its sorting and not allowing
//duplicates properties.
private static SortedSet<String> balanced(String prefix, String s){

SortedSet<String> set = new TreeSet<String>();

int len = s.length();

//base case
if (len == 0){

//return the new SortedSet with just the prefix
return set;

}
else{

SortedSet<String> rest = new TreeSet<String>();

for(int i = 0; i<len; i++){

//get all permutations and store in a SortedSet, rest
rest = balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));

//put each permutation into the new SortedSet
}

return set;

}
}
```

}