All permutations of a string
The question
Generate all permutations of a given string.
My solution
This is a question that I had been asked before and I wasn’t able to solve in the duration of an interview. I took some time to think about the problem and this is what I came with.
There are going to be n! permutations so that is what I should expect. The permutations of a string of length 1 is the string itself. The permutations for a string of length two is the string and the reversed string. With this in mind I came up with this recursive algorithm: