The answer given by Ben is wrong, as it is not printing a permutation of the string. For example, given abc, the permutation of abc will result in abc acb bca bac cab cba The complexity of the algorithm described below is (n!) as the permutation of any string will result in printing the string n! times. First of all, an example to illustrate the algorithm. Given "abc", select the first character in this case "a" permute the remainder, "bc" of the string with the new list, push a into all possible positions pseoducode: function ArrayList permute(String s) { ArrayList permutations if string is null, return null, if string length is equal to zero, add an empty string into the permutations array list a = first character in string remainder = string.substring(1); ArrayList permutedRemainder = permute(remainder); //here's where the n! complexity comes in for every value in permutedRemainder { for(int position = 0; position < string.length; position++) { permutations.add(merge(string, first letter, position); } } return the ArrayList permutations } the only thing left is to write a merge function which will insert the given character into the given position in the string.

this was my last interview, was tired, and didn't make progress till I ran out of time. Definitely should have ran through a couple practice problems before the interview.