Java Program to find all Permutations of a String

Filed Under: Java

Finding all permutations of a String in a Java Program is a tricky question and asked many times in interviews.

Permutation of String in Java Algorithm

To get all the permutations, we will first take out the first char from String and permute the remaining chars.

If String = “ABC”

First char = A and remaining chars permutations are BC and CB.

Now we can insert first char in the available positions in the permutations.

BC -> ABC, BAC, BCA

CB -> ACB, CAB, CBA

So we can write a recursive function call to return the permutations and then another function call to insert the first characters to get the complete list of permutations.


package com.journaldev.java.string;

import java.util.HashSet;
import java.util.Set;

/**
 * Java Program to find all permutations of a String
 * @author pankaj
 *
 */
public class StringFindAllPermutations {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        //Handling error scenarios
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); // first character
        String rem = str.substring(1); // Full string without first character
        Set<String> words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0;i<=strNew.length();i++){
                perm.add(charInsert(strNew, initial, i));
            }
        }
        return perm;
    }

    public static String charInsert(String str, char c, int j) {
        String begin = str.substring(0, j);
        String end = str.substring(j);
        return begin + c + end;
    }

    public static void main(String[] args) {
        String s = "AAC";
        String s1 = "ABC";
        String s2 = "ABCD";
        System.out.println("\nPermutations for " + s + " are: \n" + permutationFinder(s));
        System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
        System.out.println("\nPermutations for " + s2 + " are: \n" + permutationFinder(s2));
    }
}

Note that I have used SET to remove duplicates so that it works for those strings also having same chars.

Here is the output of the above program:


Permutations for AAC are: 
[AAC, ACA, CAA]

Permutations for ABC are: 
[ACB, ABC, BCA, CBA, CAB, BAC]

Permutations for ABCD are: 
[DABC, CADB, BCAD, DBAC, BACD, ABCD, ABDC, DCBA, ADBC, ADCB, CBDA, CBAD, DACB, ACBD, CDBA, CDAB, DCAB, ACDB, DBCA, BDAC, CABD, BADC, BCDA, BDCA]

That’s all for finding all permutations of a String in Java.

You can download the example program code from our GitHub Repository.

Comments

  1. Datt says:

    Hi Pankaj

    Thanks for your program!

    When I ran the flow with some input, it throws StringIndexOutOfBoundException.

    While debugging the flow, I could not find any kind of string data getting stored into the variable “words” in the statement Set words = permutationFinder();

    Also, lets take the input as ABC. In the first iteration, it takes the rem as BC, and further the rem goes to empty string. So, it has been observed that the flow can never reach the for loop. Please check and let me know if I am going wrong in my understanding anywhere. The same kind of code I found at crunchify.com with method names different.

    Thank you

  2. Santy says:

    Code to accept User input and display permutations using the recursive method.

    public class PermutationExample {
    public static void main(String args[]) throws Exception {
    Scanner input = new Scanner(System.in);
    System.out.print(“Enter String: “);
    String chars = input.next();
    showPermutations(“”, chars);
    }
    public static void showPermutations(String str, String chars) {
    if (chars.length() <= 1)
    System.out.println(str + chars);
    else
    for (int i = 0; i < chars.length(); i++) {
    try {
    String newString = chars.substring(0, i)
    + chars.substring(i + 1);
    showPermutations(str + chars.charAt(i), newString);
    } catch (Exception e) {
    e.printStackTrace();
    }
    }
    }
    }

  3. Baljinder kaur says:

    thanks for code
    that’s a huge help for me

  4. Aman says:

    Why are we using Set for Permutations , the output for any string with repeating characters would be Combinations and not Permutations.
    We should be using List instead of Set.
    Please let me know if I am wrong.

    1. Avi says:

      just to remove duplication.

  5. Pragya says:

    Java code which will print all possible permutation of any string .,and string will provided at runtime by user…plz help me..

    1. Pankaj says:

      Just extend the program to use Scanner class to get input from the user.

  6. Siyabonga Mdletshe says:

    public static void permute(String string){
    permute(“”, string);
    }
    private static void permute(String permutation, String remainingCharacters){
    if(remainingCharacters==null){
    return;
    }
    else if(remainingCharacters.length()==0){//print permutation for the first character
    System.out.println(permutation);
    }
    for(int i =0; i<remainingCharacters.length();i++){
    char firstChar=remainingCharacters.charAt(i);//first character to permute
    permute(permutation+firstChar,remainingCharacters.substring(0,i)+remainingCharacters.substring(i+1));//add char to the permutation and permute the remaining characters
    }
    }

    1. Aditya says:

      Could you please explain the above procedure

    2. Nayakam Vishnuvardhan says:

      is this works no where you are assigning the result

    3. Nayakam Vishnuvardhan says:

      This is for first set of values abc , aca debugged output. if input if “abc”

      a bc
      ab c
      abc

      here how the the second word is changed to c.

      ac b
      acb

      please explain how is that changed.

  7. Manoj says:

    Set words = permutationFinder(rem);
    Why this line is used

  8. vaibhav dave says:

    Hi Pankaj,
    Thanks for the post. I think the set which is declared inside method findPermutation should have been passed to method. Coz , everytime a new instance is created…which will not provide expected result.

  9. vaibhav dave says:

    Hi Pankaj ,
    While referring to your above code , I found a bug. I think you are creating new HashSet inside permutationFinder() method , which is wrong. The set should have been passed as a parameter to the method , then only it would give all permutations. Otherwise , it would give for only last iteration.

  10. Ashok says:

    I run this code for a abc. I got only output cba. Please help me

  11. Brijesh says:

    String permutation in java simple and easy way. please correct me if my logic is wrong.


    package com.java.programming;

    import java.util.ArrayList;
    import java.util.LinkedHashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Map.Entry;

    /**
    * @author Brijesh
    *
    */
    public class StringPermutatio {

    public static void main(String[] args) {
    String input = "ABCD";
    System.out.println(genPermutation(input).toString());
    }

    public static List genPermutation(String input) {
    Map firstMap = new LinkedHashMap();
    Map secondMap = new LinkedHashMap();
    List output = new ArrayList();

    char[] chr = input.toCharArray();
    for (int i = 0; i < chr.length; i++) {
    firstMap.put(Character.valueOf(chr[i]), String.valueOf(chr[i]));
    secondMap.put(Character.valueOf(chr[i]), String.valueOf(chr[i]));
    }

    for (Entry chr1 : firstMap.entrySet()) {
    for (Entry chr2 : secondMap.entrySet()) {
    if (chr1.getValue().equals(chr2.getValue())) {
    output.add(String.valueOf(chr1.getValue()));
    } else {
    output.add(String.valueOf(chr1.getValue())
    + String.valueOf(chr2.getValue()));
    }
    }
    }

    return output;
    }

    }

    1. Shesh narayan says:

      Hey Brijesh/Team

      This logic in not OK..
      I think it will output only 2 Characters String. If i put my name as SHESH then it will give Output as
      SE, HS, H, HE, ES … etc. BUT actual output should be 5 character String like HHSES, HHSSE, SEHHS, ESSHH, SSEHH etc…..
      If i am wrong plz let me know.

  12. Anwita Ghosh Dastidar says:

    I am student of class 11, living in Kolkata.
    And I am very much interested in computer programming especially in Java.
    So this particular problem has been given to us as a project.
    I tried to solve it on my own.
    However, I failed.
    I asked a classmate for some help, but she failed to figure out the logic too.
    We both thought a lot.
    We ended up with a solution which works only if we know the word before hand.
    It was a very idiotic one as we had to write n number of for loops if we had to find out the permutation of a word with n number of alphabets.
    We rejected it.
    Then we thought about using the Mathematical portion.
    We thought of creating an array which would store all the letter of the word.
    And then another which would store all the permutations.
    We could figure out the number of cells needed by calculating the factorial of the number of words.
    We have even figured out how to cancel the printing of the words that have already been printed.
    Then suddenly we discovered that all permutations are even and half are reverse of the permutation.
    So, if we need to find out the permutation of ABCD.
    Instead of figuring all 24(4!) possibilities, we can just figure out one half and then we can reverse them.
    Which are..
    ABCD
    ABDC
    ACBD
    ACDB
    ADBC
    ADCB
    BACD
    BADC
    BCAD
    BDAC
    CABD
    CBAD
    None of them are common none of them are reverse of each other.
    Now we can’t figure out any logic to figure out these..
    That’s where we need some help.

    Now you’d say to just use your program.
    But there’s a small problem.
    There are some functions and other logics you have use which we haven’t yet been taught.
    So obviously we can’t use them.
    So if you can just give a solution using arrays and string and scanner and reverse function and all low level functions it would be much help 🙂

    1. Siddu says:

      package Strings;

      public class PermitationString {
      public static void main(String[] args) {
      String s = “ABC”;
      permutation(s);
      }
      public static void permutation(String str) {
      permutation(“”, str);
      }

      private static void permutation(String prefix, String str) {
      int n = str.length();
      if (n == 0)
      System.out.println(prefix);
      else {
      for (int i = 0; i < n; i++)
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
      }
      }
      }

      1. Mozib says:

        Wow! nice logic thanks for posting.

        Mozib

  13. Rashmi says:

    Hi Pankaj,

    Thank you for the post. Its very clear and easy. What is the ime complexity and of the program?

    1. Rudra says:

      There are n! permutations it will take O(n!) time.

  14. rajni says:

    Its really very easy to understand!! Thanks!!

  15. Bhavya says:

    Hi Pankaj,

    Thats a good code you have written there. However, I just have one suggestion which will improve the performance of this code. In you method:

    public static String charInsert(String str, char c, int j) {
    String begin = str.substring(0, j);
    String end = str.substring(j);
    return begin + c + end;
    }

    Your return statement is actually creating 2 more new strings, since the “+” operator creates a new string rather than appending to the existing string. I would rather have a StringBuffer do this thing, since it gives a better performance and is built for cases where you would want to change ur string constantly before a final version.

    Hope that helps!

    Thanks!

    1. Pankaj says:

      Thanks for the suggestion, however StringBuilder will give even better performance. 🙂

      1. Bhavya says:

        Yes. I did mean StringBuilder. I tend to get confused between the two very often.

  16. Anitha Reddy says:

    Hi Pankaj,

    superb man…………

    Thank you for the post. really good to easy understand.

    1. Vijay says:

      I didn’t understand the logic can you please explain in simple form.

      I understand below logic

      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));

      its really very hard from me to understand it if possible can you please explain

  17. srinivasa.v says:

    please write the code for

    input value is :String str=”KriSHnA”
    output value is String str=”kRIshNa”

    i..e., if we taken case sensitive string in the output string should be opposite in there case sensitivity.

    1. Praveen says:

      public static void reversCase(String str)
      {
      String newStr = “”;
      for(int i=0; i<str.length(); i++) {
      if(str.charAt(i) == str.toUpperCase().charAt(i))
      newStr += str.toLowerCase().charAt(i);
      if(str.charAt(i) == str.toLowerCase().charAt(i))
      newStr += str.toUpperCase().charAt(i);
      }
      System.out.println(newStr);
      }

  18. Tahmid says:

    Excellent one! I was finding just this one!

  19. prasad says:

    using a.b.c=c.b.a; statement how to write java program ?

  20. Nizamuddin says:

    a.b.c=c.b.a

    write a program to make the above statement in valid .remember this is not class or interface .do it

    1. Nizamuddin says:

      sorry

      write a program to make the above statement is valid in program .remember this is not class or interface.

      1. Pankaj says:

        I am not sure what you are trying to convey in the comment, care to explain?

  21. ASHISH MISHRA says:

    for (int i = 0; i perm.add(charInsert(strNew, initial, i));

    can u explain me what this mean…. as it is showing error ….
    And (String strNew : words)
    conversion is not done…
    check this program

    1. Pankaj says:

      Hi Ashish,

      Looks like code got corrupted and some lines are removed when I posted it here, I have updated it and it’s working fine now.

      Thanks for the input, you can try the updated program and it will work.

      1. Altaf Ahmad says:

        Hi Pankaj,

        Thank you for this program.

        Can you please explainend the program once by taking an example ?
        I m understanding the logic clearly but have some doubt how its traversing.

        Thanks in Advace

        1. Pankaj says:

          run program in Eclipse in debug mode and see how it’s getting calculated. That would solve all your doubts.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages