Java Program to print all permutation of a String?

Interviewer may start with a very basic question as to what is number of permutations of a string with n characters. In case repetition is not allowed then it would be n!  i.e  [n*(n-1)*(n-2*....*!)]  . if repetition is allowed it would be n^n i.e [n*n*...n times].

Next would be to code it actually. Generally language is not a concern. What interviewer looks is how candidate thinks(his solving ability) and whether he is able to complete error free and working code. Following is a Java code that will print permutations of a given String along with the number of permutations possible.

Example :

Code : 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

/**  * Created with IntelliJ IDEA.  * User: aniket  * Date: 11/19/13  * Time: 3:16 PM  */ public class PermutationsPrinter {     private int noOfPermutation;     public void permute(char[] line,int start, int end){         int j;         if(start == end){             noOfPermutation++;             System.out.println(line);         }         else {             for(j=start;j<=end;j++){                 char[] newLine = getSwappedString(line, start, j);                 permute(newLine,start+1,end);             }         }     }         private char[] getSwappedString(char[] characters,int i,int j ){         String newLine = String.valueOf(swap(characters,i,j));//Create New String         swap(characters,i,j);//restore original String         return newLine.toCharArray();     }         private char[] swap(char[] characters,int i,int j){         char temp = characters[i];         characters[i] = characters[j];         characters[j] = temp;         return characters;     }         public int getNoOfPermutation() {         return noOfPermutation;     }         public static void main(String args[]){         String line = "ABC";         PermutationsPrinter permuter = new PermutationsPrinter();         permuter.permute(line.toCharArray(), 0, line.length() - 1);         System.out.println("Number Of Permutations made : " + permuter.getNoOfPermutation());     } }

Output  : 

ABC

ACB

BAC

BCA

CBA

CAB

Number Of Permutations made : 6

(3! = 6 as expected)

More better example where you don't have to swap again to restore string is provided in the Interview questions git repo -

• Print All String Permuatation