Tutorial

How to find all permutation of a String in Java

Published on August 4, 2022
author

Pankaj

How to find all permutation of a String in Java

In this tutorial, we will learn how to find the permutation of a String in a Java Program. It’s a tricky question and asked mostly in Java interviews.

Algorithm for Permutation of a String in Java

We will first take the first character from the String and permute with 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 We can write a recursive function to return the permutations and then another function to insert the first characters to get the complete list of permutations.

Java Program to Print Permutations of a String

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));
    }
}

I have used Set to store the string permutations. So that duplicates are removed automatically.

Output

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.

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Learn more about our products

About the author(s)

Category:
Tutorial
Tags:

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

Still looking for an answer?

Ask a questionSearch for more help

Was this helpful?
 
JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
February 14, 2013

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

- ASHISH MISHRA

JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
March 2, 2013

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.

- Pankaj

JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
November 8, 2013

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

- Altaf Ahmad

JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
November 11, 2013

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

- Pankaj

    JournalDev
    DigitalOcean Employee
    DigitalOcean Employee badge
    August 10, 2013

    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

    - Nizamuddin

    JournalDev
    DigitalOcean Employee
    DigitalOcean Employee badge
    August 10, 2013

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

    - Nizamuddin

    JournalDev
    DigitalOcean Employee
    DigitalOcean Employee badge
    August 11, 2013

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

    - Pankaj

      JournalDev
      DigitalOcean Employee
      DigitalOcean Employee badge
      August 16, 2013

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

      - prasad

        JournalDev
        DigitalOcean Employee
        DigitalOcean Employee badge
        October 10, 2013

        Excellent one! I was finding just this one!

        - Tahmid

          JournalDev
          DigitalOcean Employee
          DigitalOcean Employee badge
          October 18, 2013

          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.

          - srinivasa.v

          JournalDev
          DigitalOcean Employee
          DigitalOcean Employee badge
          May 10, 2019

          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); }

          - Praveen

            JournalDev
            DigitalOcean Employee
            DigitalOcean Employee badge
            May 22, 2014

            Hi Pankaj, superb man… Thank you for the post. really good to easy understand.

            - Anitha Reddy

            JournalDev
            DigitalOcean Employee
            DigitalOcean Employee badge
            March 14, 2018

            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

            - Vijay

              JournalDev
              DigitalOcean Employee
              DigitalOcean Employee badge
              June 27, 2014

              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!

              - Bhavya

              JournalDev
              DigitalOcean Employee
              DigitalOcean Employee badge
              June 29, 2014

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

              - Pankaj

              JournalDev
              DigitalOcean Employee
              DigitalOcean Employee badge
              July 20, 2014

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

              - Bhavya

                JournalDev
                DigitalOcean Employee
                DigitalOcean Employee badge
                August 13, 2014

                Its really very easy to understand!! Thanks!!

                - rajni

                  JournalDev
                  DigitalOcean Employee
                  DigitalOcean Employee badge
                  September 12, 2014

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

                  - Rashmi

                  JournalDev
                  DigitalOcean Employee
                  DigitalOcean Employee badge
                  September 17, 2018

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

                  - Rudra

                    JournalDev
                    DigitalOcean Employee
                    DigitalOcean Employee badge
                    September 23, 2014

                    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 :)

                    - Anwita Ghosh Dastidar

                    JournalDev
                    DigitalOcean Employee
                    DigitalOcean Employee badge
                    January 6, 2016

                    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)); } } }

                    - Siddu

                    JournalDev
                    DigitalOcean Employee
                    DigitalOcean Employee badge
                    December 28, 2016

                    Wow! nice logic thanks for posting. Mozib

                    - Mozib

                      JournalDev
                      DigitalOcean Employee
                      DigitalOcean Employee badge
                      January 17, 2015

                      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; } }

                      - Brijesh

                      JournalDev
                      DigitalOcean Employee
                      DigitalOcean Employee badge
                      September 14, 2015

                      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.

                      - Shesh narayan

                        JournalDev
                        DigitalOcean Employee
                        DigitalOcean Employee badge
                        October 2, 2015

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

                        - Ashok

                          JournalDev
                          DigitalOcean Employee
                          DigitalOcean Employee badge
                          January 25, 2016

                          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.

                          - vaibhav dave

                            JournalDev
                            DigitalOcean Employee
                            DigitalOcean Employee badge
                            January 26, 2016

                            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.

                            - vaibhav dave

                              JournalDev
                              DigitalOcean Employee
                              DigitalOcean Employee badge
                              August 23, 2016

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

                              - Manoj

                                JournalDev
                                DigitalOcean Employee
                                DigitalOcean Employee badge
                                September 12, 2016

                                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 } }

                                - Siyabonga Mdletshe

                                JournalDev
                                DigitalOcean Employee
                                DigitalOcean Employee badge
                                September 22, 2017

                                Could you please explain the above procedure

                                - Aditya

                                  JournalDev
                                  DigitalOcean Employee
                                  DigitalOcean Employee badge
                                  December 1, 2018

                                  is this works no where you are assigning the result

                                  - Nayakam Vishnuvardhan

                                    JournalDev
                                    DigitalOcean Employee
                                    DigitalOcean Employee badge
                                    December 1, 2018

                                    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.

                                    - Nayakam Vishnuvardhan

                                      JournalDev
                                      DigitalOcean Employee
                                      DigitalOcean Employee badge
                                      September 26, 2016

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

                                      - Pragya

                                      JournalDev
                                      DigitalOcean Employee
                                      DigitalOcean Employee badge
                                      May 31, 2018

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

                                      - Pankaj

                                        JournalDev
                                        DigitalOcean Employee
                                        DigitalOcean Employee badge
                                        March 7, 2017

                                        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.

                                        - Aman

                                        JournalDev
                                        DigitalOcean Employee
                                        DigitalOcean Employee badge
                                        September 1, 2017

                                        just to remove duplication.

                                        - Avi

                                          JournalDev
                                          DigitalOcean Employee
                                          DigitalOcean Employee badge
                                          October 17, 2018

                                          thanks for code that’s a huge help for me

                                          - Baljinder kaur

                                            JournalDev
                                            DigitalOcean Employee
                                            DigitalOcean Employee badge
                                            January 30, 2019

                                            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(); } } } }

                                            - Santy

                                              JournalDev
                                              DigitalOcean Employee
                                              DigitalOcean Employee badge
                                              July 16, 2019

                                              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

                                              - Datt

                                                JournalDev
                                                DigitalOcean Employee
                                                DigitalOcean Employee badge
                                                September 22, 2019

                                                public class GFG { static void printPermutn(String str, String ans) { if (str.length() == 0) { System.out.print(ans + " "); // str.length() is ‘0’ } for (int i = 0; i < str.length(); i++) { // str.length is not ‘0’ … Can you Explain this Please. char ch = str.charAt(i); String ros = str.substring(0, i) + str.substring(i + 1); printPermutn(ros, ch+ans); } } public static void main(String[] args) { String s = “abc”; printPermutn(s, “”); } }

                                                - Hemanth

                                                  JournalDev
                                                  DigitalOcean Employee
                                                  DigitalOcean Employee badge
                                                  June 17, 2020

                                                  I stole your code to write a method that checks whether any permutation ↴ of an input string is a palindrome. Thanks! import java.util.*; class Movies { public static boolean hasPalindromePermutation(String input){ String[] strArray = permute(input).toArray(new String[0]); for(String cur : strArray){ if(cur.equals(isPalindrome(cur))){ return true; } } return false; } public static Set permute(String str){ Set perm = new HashSet(); //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 words = permute(rem); for (String strNew : words) { // System.out.println(strNew); for (int i = 0; i<=strNew.length(); i++){ perm.add(swapper(strNew, initial, i)); } } return perm; } public static String swapper(String str, char c, int j) { String begin = str.substring(0, j); String end = str.substring(j); return begin + c + end; } public static String isPalindrome(String str){ char[] arr = str.toCharArray(); int low = 0; int high = arr.length-1; char temp; while(low<high){ temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; low++; high–; } String result = new String(arr); return result; } public static void main(String[ ] args) {; System.out.println(hasPalindromePermutation(“civic”)); } }

                                                  - Beto

                                                    JournalDev
                                                    DigitalOcean Employee
                                                    DigitalOcean Employee badge
                                                    July 16, 2019

                                                    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

                                                    - Datt

                                                      JournalDev
                                                      DigitalOcean Employee
                                                      DigitalOcean Employee badge
                                                      September 22, 2019

                                                      public class GFG { static void printPermutn(String str, String ans) { if (str.length() == 0) { System.out.print(ans + " "); // str.length() is ‘0’ } for (int i = 0; i < str.length(); i++) { // str.length is not ‘0’ … Can you Explain this Please. char ch = str.charAt(i); String ros = str.substring(0, i) + str.substring(i + 1); printPermutn(ros, ch+ans); } } public static void main(String[] args) { String s = “abc”; printPermutn(s, “”); } }

                                                      - Hemanth

                                                        JournalDev
                                                        DigitalOcean Employee
                                                        DigitalOcean Employee badge
                                                        June 17, 2020

                                                        I stole your code to write a method that checks whether any permutation ↴ of an input string is a palindrome. Thanks! import java.util.*; class Movies { public static boolean hasPalindromePermutation(String input){ String[] strArray = permute(input).toArray(new String[0]); for(String cur : strArray){ if(cur.equals(isPalindrome(cur))){ return true; } } return false; } public static Set permute(String str){ Set perm = new HashSet(); //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 words = permute(rem); for (String strNew : words) { // System.out.println(strNew); for (int i = 0; i<=strNew.length(); i++){ perm.add(swapper(strNew, initial, i)); } } return perm; } public static String swapper(String str, char c, int j) { String begin = str.substring(0, j); String end = str.substring(j); return begin + c + end; } public static String isPalindrome(String str){ char[] arr = str.toCharArray(); int low = 0; int high = arr.length-1; char temp; while(low<high){ temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; low++; high–; } String result = new String(arr); return result; } public static void main(String[ ] args) {; System.out.println(hasPalindromePermutation(“civic”)); } }

                                                        - Beto

                                                          JournalDev
                                                          DigitalOcean Employee
                                                          DigitalOcean Employee badge
                                                          July 16, 2019

                                                          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

                                                          - Datt

                                                            JournalDev
                                                            DigitalOcean Employee
                                                            DigitalOcean Employee badge
                                                            September 22, 2019

                                                            public class GFG { static void printPermutn(String str, String ans) { if (str.length() == 0) { System.out.print(ans + " "); // str.length() is ‘0’ } for (int i = 0; i < str.length(); i++) { // str.length is not ‘0’ … Can you Explain this Please. char ch = str.charAt(i); String ros = str.substring(0, i) + str.substring(i + 1); printPermutn(ros, ch+ans); } } public static void main(String[] args) { String s = “abc”; printPermutn(s, “”); } }

                                                            - Hemanth

                                                              JournalDev
                                                              DigitalOcean Employee
                                                              DigitalOcean Employee badge
                                                              June 17, 2020

                                                              I stole your code to write a method that checks whether any permutation ↴ of an input string is a palindrome. Thanks! import java.util.*; class Movies { public static boolean hasPalindromePermutation(String input){ String[] strArray = permute(input).toArray(new String[0]); for(String cur : strArray){ if(cur.equals(isPalindrome(cur))){ return true; } } return false; } public static Set permute(String str){ Set perm = new HashSet(); //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 words = permute(rem); for (String strNew : words) { // System.out.println(strNew); for (int i = 0; i<=strNew.length(); i++){ perm.add(swapper(strNew, initial, i)); } } return perm; } public static String swapper(String str, char c, int j) { String begin = str.substring(0, j); String end = str.substring(j); return begin + c + end; } public static String isPalindrome(String str){ char[] arr = str.toCharArray(); int low = 0; int high = arr.length-1; char temp; while(low<high){ temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; low++; high–; } String result = new String(arr); return result; } public static void main(String[ ] args) {; System.out.println(hasPalindromePermutation(“civic”)); } }

                                                              - Beto

                                                                Try DigitalOcean for free

                                                                Click below to sign up and get $200 of credit to try our products over 60 days!

                                                                Sign up

                                                                Join the Tech Talk
                                                                Success! Thank you! Please check your email for further details.

                                                                Please complete your information!

                                                                Become a contributor for community

                                                                Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

                                                                DigitalOcean Documentation

                                                                Full documentation for every DigitalOcean product.

                                                                Resources for startups and SMBs

                                                                The Wave has everything you need to know about building a business, from raising funding to marketing your product.

                                                                Get our newsletter

                                                                Stay up to date by signing up for DigitalOcean’s Infrastructure as a Newsletter.

                                                                New accounts only. By submitting your email you agree to our Privacy Policy

                                                                The developer cloud

                                                                Scale up as you grow — whether you're running one virtual machine or ten thousand.

                                                                Get started for free

                                                                Sign up and get $200 in credit for your first 60 days with DigitalOcean.*

                                                                *This promotional offer applies to new accounts only.