Interview Question: String Permutation

There are lot of question we encounter during an interview but there are few question which repeats in many interviews. But due to our lousy nature, every time we end up begging mercy to change the question. My friend has gone through such painful experience many time. But this time he can not resist himself to find the solution of the question. Though he could not find the solution and ask me to relieve his burden. So I thought of enlighten world with my half cooked knowledge.

Question: Find all the permutation of a string?
Condition A: Find if all characters of the string are unique?

Answer: How should be start writing the code? If you look at the permutation mechanism it has a certain pattern. Lets examine it with different possible combination of string ABC

   1: --- Start with A ---

   2: ABC

   3: ACB

   4: --- Start with B ---

   5: BAC

   6: BCA

   7: --- Start with C ---

   8: CAB

   9: CBA

Ok, it is still less clear can we look for a bigger example. Lets look for ABCD

   1: --- Starting with A---

   2: A BCD

   3: A BDC

   4: A CBD

   5: A CDB

   6: A DBC

   7: A DCB

   8:  

   9: --- Starting with B ---

  10: B ACD

  11: B ADC

  12: B CAD

  13: B CDA

  14: B DAC

  15: B DCA

  16:  

  17: --- Starting with C ---

  18: CABD

  19: CADB

  20: CBAD

  21: CBDA

  22: CDAB

  23: CDBA

  24:  

  25: ----Starting with D---

  26: DABC

  27: DACB

  28: DBAC

  29: DBCA

  30: DCAB

  31: DCBA

Now from above 2 code snippets it is clear puzzle for n can be broken into n-1 elements. If there are 4 elements then add 4th element to permutations of rest 3… Yes, you got the solution. It is a recursive process. Where we need to touch the bottom of the ocean and then return to water surface.

Code:

1: import java.util.ArrayList;

   2: import java.util.LinkedList;

   3: import java.util.List;

   4:  

   5: public class StringPermutations {

   6:  

   7:     List<String> strs = new LinkedList<String>();

   8:         

   9:     void printString(String str){

  10:         char[] charArray = str.toCharArray();

  11:         List<Character> charList = new ArrayList<Character>();

  12:         for(char ch: charArray){

  13:             charList.add(ch);

  14:         }

  15:         printCharacterArray(charList, new StringBuffer());

  16:         System.out.println(strs);

  17:     }

  18:  

  19:     private void printCharacterArray(List<Character> charList, StringBuffer temp) {

  20:         

  21:         StringBuffer savePoint = new StringBuffer(temp);

  22:         for(int index = 0; index <  charList.size(); index++){            

  23:             temp = new StringBuffer(savePoint);

  24:             temp.append(charList.get(index));

  25:             List<Character> tempChars = new ArrayList<Character>(charList);

  26:             tempChars.remove(index);

  27:             printCharacterArray(tempChars, temp);

  28:         }

  29:         if(charList.size() == 0){

  30:             strs.add(temp.toString());

  31:         }

  32:         temp = new StringBuffer();

  33:     }    

  34: }

Explanation:
In the above listing I have strs variable which keeps all the list.
printString method converts string into list of character and calls recursive function.
printCharacterScreen is a recursive method which iterate through the each element of the list and calls the same method again with list – element. The recursion breaks when there are no elements in the list then it adds the str to the list.
To run this code, copy the above code and save it to StringPermutations.java file. Add the following code of snippet.

1: public static void main(String[] args){

   2:     StringPermutations sp = new StringPermutations();

   3:     sp.printString("ABCD");

   4: }

Compile and run the class. It will print all combination of the ABCD string.

Condition B: if string has non-unique characters?
No issues, use java’s collection API well. Use Set instead of list to save all the string.

Disclaimer: The algo written here may not be performant. If you have some other algorithm which takes solves issue in lesser time complexity please let me know.