Here is the interview question prompt, presented for reference.

Write an algorithm that takes an input string like "abc", and prints out all possible permutations of the string. A permutation of a group of elements is defined as one of the n! number possible arrangements the elements can take, where n is the number of elements in the range.

We'd expect the following to hold true, note the permutations printed out:

const str = "abc"
permutations(str)
// abc
// acb
// bac
// bca
// cba
// cab

String str = "abc";
permutations(str);
// abc
// acb
// bac
// bca
// cba
// cab

str = "abc"
permutations(str)
# abc
# acb
# bac
# bca
# cba
# cab

std::string str = "abc";
permutations(str);
// abc
// acb
// bac
// bca
// cba
// cab

string str = "abc";
Permutations(str);
// abc
// acb
// bac
// bca
// cba
// cab

str := "abc"
permutations(str)
// abc
// acb
// bac
// bca
// cba
// cab

A hint here: break the problem down, and think about what steps are going to be repeated. How would we get from "abc" to "acb"?

Constraints

• The string will only consist of lowercase letters
• Length of the string <= 7
• Expected time complexity : O(n*n!)
• Expected space complexity : O(n*n!)

You can see the full challenge with visuals at this link.