Tutorial

How to find all permutation of a String in Java

Published on August 3, 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 authors
Default avatar
Pankaj

author

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
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
    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
      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
        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
          October 17, 2018

          thanks for code that’s a huge help for me

          - Baljinder kaur

            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 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
                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
                  August 23, 2016

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

                  - Manoj

                    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

                      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!

                      Featured on Community

                      Get our biweekly newsletter

                      Sign up for Infrastructure as a Newsletter.

                      Hollie's Hub for Good

                      Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

                      Become a contributor

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

                      Welcome to the developer cloud

                      DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.

                      Learn more