Write a method in Java that will find and print out all the possible combinations (or “permutations”) of the characters in a string. So, if the method is given the string “dog” as input, then it will print out the strings “god”, “gdo”, “odg”, “ogd”, “dgo”, and “dog” – since these are all of the possible permutations of the string “dog”. Even if a string has characters repeated, each character should be treated as a distinct character – so if the string “xxx” is input then your method will just print out “xxx” 6 times.

Finding an algorithm to answer this question may seem challenging because finding all the different permutations of a string is something that you just do naturally without really thinking about it. But, try to figure out what algorithm you are implicitly using in your mind whenever you write down all the different permutations of a string. Let’s use the word “dogs” as an example and see what different permutations we get. Here is what comes up when we list out all the possible permutations of the letters in “dogs”:

dogs sgod gsod ogsd
dosg sgdo gsdo ogds
dsgo sdgo gdso osdg
dsog sdog gdos osgd
dgso sodg gods odgs
dgos sogd gosd odsg




So, when we came up with the permutations of “dogs” above, how did we do it? What were we implicitly thinking? Well, it looks like what we did in each column was choose one letter to start with, and then we found all the possible combinations for the string beginning with that letter. And once we picked a letter in the 2nd position, we then found all the possible combinations that begin with that 2 letter sequence before we changed any of the letters in the first 2 positions. So, basically what we did was choose a letter and then peformed the permutation process starting at the next position to the right before we come back and change the character on the left.

Finding the permutations with recursion

Our description of the process that we followed sounds a lot like something that could be solved with recursion. How can we change our description so that it’s easier to write out in a recursive method? Let’s phrase it like this: In order to find all possible combinations for a given string, then start at a position x, then find and place all possible letters in position x. Every time we put a new letter in position x, we should then find all the possible combinations at position x+1 – this would be the recursive call that we make. How do we know when to print out a string? Well, when we are at a position x that is greater than the number of letters in the input string, then we know that we have found one valid combination/permutation of the string and then we can print it out and return to changing letters at positions less than x. This would be our base case – remember that we always must have a recursive case and a base case when using recursion.

Which letters can we use in a given position?




Another big part of this problem is figuring out which letters we can put in a given position. Using our sample string “dogs”, lets say that we are going through all the permutations where the first 2 letters are “gs”. Then, it should be clear that the letters in the 3rd or 4th position can only be either “d” or “o”, because “g” and “s” were already used. As part of our algorithm, we have to know which letters can be used in a given position – because we can’t reuse the letters that were used in the earlier positions. And in order to do this we can simply have an array of Boolean values that correspond to the positions of the letters in the input string – so if a certain character from the input string has already been used, then it’s position in the array would be set to “true”.

Find all the permutations of a string in Java

Now, here is what the Java method would like for our algorithm:

void permute( String input)
{
  int inputLength = input.length();
  boolean[ ] used = new boolean[ inputLength ];
  StringBuffer outputString = new StringBuffer();
  char[ ] in = input.toCharArray( );
  
  doPermute ( in, outputString, used, inputLength, 0 );

}

  void doPermute ( char[ ] in, StringBuffer outputString, 
                    boolean[ ] used, int inputlength, int level)
  {
     if( level == inputLength) {
     System.out.println ( outputString.toString()); 
     return;
     }

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

       if( used[i] ) continue;

       outputString.append( in[i] );      
       used[i] = true;       
       doPermute( in,   outputString, used, length, level + 1 );       
       used[i] = false;       
         outputString.setLength(   outputString.length() - 1 );   
    }
 }

If you are wondering why we used StringBuffer instead of String in the code above - you can read more about that here: String vs StringBuffer.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • Arthur

    Another way to implement this:
    (note: the code could be enhanced in a lot of ways, by using a StringBuilder for instance, and properly naming the parameters, this is just a quick and dirty implementation)

    public static void main (String[] args) {
    System.out.print(R(“”, “abcd”));
    }

    public static String R(String x, String y) {
    String s = “”;
    if(y.length() == 1) {
    s += x + y + ” “;
    }
    else {
    for(int i = 0; i < y.length(); i++) {
    s += R(x + y.substring(i, i + 1),
    y.substring(0, i) + y.substring(i + 1, y.length()));
    }
    }
    return s;
    }

  • cynicthnkr

    thanks ahmed.

  • Ahmed Elsayed

    Hi Cynicthnkr

    1) yes it is the same variable as input Length as when you look at the if statement in the base case, it will be comparing level which is incremented by the recursive call with inputLength. Remember inputLength has to stay constant as a permutation is the same length as the original string

    2) what this does is as he is creating the string in the StringBuffer, as each character is used we no longer want to use it and we want to focus on the other characters(example of dog used above in the explanation) he checks which character have been used by the boolean array. He then decrements the substring by 1 each time after each character is used. The only reason this is done is because as the recursive call is made, the length of the substring is always the same and as each character is already used we need to decrease it by 1.

    hope it helps 🙂

  • cynicthnkr

    Thanks for explaining. Two things i don’t get –

    1) is the length variable passed in “doPermute( in, outputString, used, length, level + 1 );” 5th line from last, same as the inputLength variable? It doesn’t seem to be declared.

    2) What does this line – “outputString.setLength( outputString.length() – 1 );” third from last does? and why is it needed?

    can anyone explain please?