Programming Interview Questions 11: All Permutations of String

The title says it all, this is a pretty standard interview question. Generate all permutations of a given string.

This may seem hard at first but it’s in fact pretty easy once we figure out the logic. Let’s say we’re given a string of length N, and we somehow generated some permutations of length N-1. How do we generate all permutations of length N? Demonstrating with a small example will help. Let the string be ‘LSE’, and we have length 2 permutations ‘SE’ and ‘ES’. How do we incorporate the letter L into these permutations? We just insert it into every possible location in both strings: beginning, middle, and the end. So for ‘SE’ the result is: ‘LSE’, ‘SLE’, ‘SEL’. And for the string ‘ES’ the results is: ‘LES’, ‘ELS’, ‘ESL’. We inserted the character L to every possible location in all the strings. This is it!. We will just use a recursive algorithm and we’re done. Recurse until the string is of length 1 by repeatedly removing the first character, this is the base case and the result is the string itself (the permutation of a string with length 1 is itself). Then apply the above algorithm, at each step insert the character you removed to every possible location in the recursion results and return. Here is the code:

def permutations(word):
    if len(word)<=1:
        return [word]
    #get all permutations of length N-1
    #iterate over all permutations of length N-1
    for perm in perms:
        #insert the character into every possible location
        for i in range(len(perm)+1):
            result.append(perm[:i] + char + perm[i:])
    return result

We remove the first character and recurse to get all permutations of length N-1, then we insert that first character into N-1 length strings and obtain all permutations of length N . The complexity is O(N!) because there are N! possible permutations of a string with length N, so it’s optimal. I wouldn’t recommend executing it for strings longer than 10-12 characters though, it’ll take a long time. Not because it’s inefficient, but inherently there are just too many permutations.

This is one of the most common interview questions, so very useful to know by heart.

VN:F [1.9.22_1171]
Rating: 8.3/10 (35 votes cast)
Programming Interview Questions 11: All Permutations of String, 8.3 out of 10 based on 35 ratings
This entry was posted in Programming Interview. Bookmark the permalink.

    another similar good question, get all generated sub strings of a string.
    for xyz, the result is : x, y, z, xy, xz, yz, xyz.
    but xy, yx are considered one result.

    • Arden

      This certainly is a great question, all combinations of a string. I can write about this one as well. Thanks for the suggestion.

      • Anonymous

        It seems to be sub sequence not sub string.

      • aduyng

        This is the function I wrote in JS to do the same thing. Can you consider if you use it for your next write-up?

        • crazy

          can you write this logic in c# or c language.. while(i–) does not works in c# since it is expecting a bool..

          • Paul Sweeney Jr

            while(i– > 0)

  • Yang

    Here is an equal java implementation:

    public static void permuteString(String beginningString, String endingString) {
    if (endingString.length() <= 1)
    System.out.println(beginningString + endingString);
    for (int i = 0; i < endingString.length(); i++) {
    try {
    String newString = endingString.substring(0, i) + endingString.substring(i + 1);

    permuteString(beginningString + endingString.charAt(i), newString);
    } catch (StringIndexOutOfBoundsException exception) {

  • Anonymous

    One more similar question I heard is to find all the combinations of input in a CSV file.

    For example if the CSV file contained the following:

    Find all combinations like apx, apy, apz…….cqz.

    The above problem can be solved easily by your recursive logic.

    This problem can be pretty easily solved using iteration. Have a one dimensional array which contains pointers to the current positions in each row. Initialize this array with 0. In an infinite loop, print the elements pointed by the array. Whenever this array reaches the last element for a particular row, initialize it back to 0 and increment the previous row’s pointer by one. Do this previous row’s increment until we reach a row which is not at the last element. The stop condition for this infinite loop will be when we are attempting to move beyond the last element of the first row.

    Sometimes, I think the non-recursive functions might be given more priority than recursive functions even though recursive functions solve the problem more elegantly and easily. The non-recursive functions occupy less space sometimes (or most of the times). This comes handy when actually your application is writing the details to a stream rather than it itself doing the processing. For a case of a CSV file having m rows each having n columns, the non-recursive function has the space complexity of O(1), whereas for the non-recursive function will have O(n^m).

    • Holden

      Could you please provide your recursive and iterative code?
      I try to write, but I don’t know what our inputs should be …

  • David

    Actually, I believe the complexity is O(n*n!). True, you are permuting n! times but each permutation requires string calculations of O(n).

    • Arden

      You’re right David. Since the difference between n! and n*n! is minimal for large n, I didn’t mention it. Thanks for pointing out though.

      • Cuneyt

        In fact, you wouldn’t see O(n*n!) in most of the literature as it’s against the idea of Big Oh notation (i.e. simplification)

  • abdus

    Thaaaanks… Great explanation….

  • Nathan

    Nice! Here’s a similar non-recursive solution:

    def permutations(word):
    current = [word[0]]
    nextLevel = []
    for letter in word[1:]:
    for fragment in current:
    for i in range(len(fragment)+1):
    nextLevel.append(fragment[:i] + letter + fragment[i:])
    current = nextLevel
    nextLevel = []
    return current

  • chirag

    char ch[10],temp;
    int i,k=1,b,f;
    printf(“enter the string”);
    temp = ch[b+1];

    • Romil

      Interesting solution. I tried this for 4 letter string -abck and got duplicate answers after 12 permutations. The iteration starts with back and reaches abck on the twelfth iteration. Post that it repeats the same output.

      I liked the solution and I think some minor change would this but still havent figured it out.

  • dew

    Hi Ardent. I loved your series of Programming interview Questions. Please post some more basic questions with solutions. That would be of great help!!!!

  • CStubing

    As far as I can tell, your method does not yield unique permutations when the same character appears in the original input more than once, for example: “aab”… you’ll return 6 permutations (N! for n=3), when there should really only be 3 permutations (3! / 2!*1!). It’s a good method, and there *is* a way to modify it to become correct… Can you? ;-)

  • Mainul Mizan

    This is a iterative java version. The idea is to generate all permutation of ch[0], then ch[0] and ch[1] and so on till ch[0] to ch[n].

    public static ArrayList allStringsI(String s) {
    ArrayList retVal = new ArrayList();

    if (s == null || s.length() == 0)
    return retVal;

    char c;

    for (int i = 0; i < s.length(); i++) {
    c = s.charAt(i);

    ArrayList loop = retVal;
    retVal = new ArrayList();

    for (String st: loop){

    for (int j = 1; j <= st.length(); j++)
    retVal.add(st.substring(0, j) + c + st.substring(j));
    return retVal;

    • ram

      What’s the complexity for this??

  • Giacomo Drago

    Great post, thank you!

    After reading it, I had an idea of an alternative solution. It is not meant to be an improvement to this algorithm, in fact it’s completely different and much more complicated (quite useless for an interview ;)). However if you are interested, here it is:

  • ajitsdeshpande


    Based on your recursive python implementation for finding string permutations, I am trying to write a python based iterative(non-recursive) implementation. So far I have got this code below which only works for a input string with 3 chars :( . Trying to expand and make it generic, any pointers would help.

    def permutations_iter(word):

    while True:

    perms = []

    result = []

    char = word[0]

    new_word = word[1:]

    if len(new_word)==2:

    perms = [new_word,”.join(reversed(new_word))]

    for perm in perms:

    #insert the character into every possible location

    for i in range(len(perm)+1):

    result.append(perm[:i] + char + perm[i:])

    return result

    if len(new_word)==2:


  • 周游

    Author:Zhou You

    using namespace std;

    void OutputPermutation(string &strdata,unsigned ileft,unsigned iright)
    if(ileft>iright) return;

    for(unsigned i=ileft;i>strdata;

    int main()
    unsigned case_num= 0;
    for(unsigned i=0;i<case_num;++i){

    return 0;

  • Raf

    great posts!
    unless I misunderstood the problem, I was having some issues implementing your algo to get all permutations. seems like the first character never gets written out. In my tests I implemented the following in JS which appears to work for all combinations. (small tweak to your algo)

    function permutate(word){
    if (!word || !word.length) return;
    if (word.length == 1) return;
    var c = word[0];
    var rem = word.substr(1);
    for (i in rem+1){
    if (i==0) continue;
    var perm = rem.substr(0, i) + c + rem.substr(i);

  • rightaw2

    With C# select method and a tiny lambda expression, this gets really simple:

    static List permutations(string thisString)
    List myResult = new List();
    if (thisString.Length <= 1)
    for (int i = 0; i thisString.Substring(i, 1) + x));
    return myResult;

  • Oguz

    Is the time complexity really O(n!)? The recursion relation is T(n) = T(n-1) + n*(n-1)!
    O(n!) means we discard the computation time of the recursive step