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.
About the author(s)
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.
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.
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.
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
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
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
run program in Eclipse in debug mode and see how it’s getting calculated. That would solve all your doubts.
- Pankaj
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
sorry write a program to make the above statement is valid in program .remember this is not class or interface.
- Nizamuddin
I am not sure what you are trying to convey in the comment, care to explain?
- Pankaj
using a.b.c=c.b.a; statement how to write java program ?
- prasad
Excellent one! I was finding just this one!
- Tahmid
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
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
Hi Pankaj, superb man… Thank you for the post. really good to easy understand.
- Anitha Reddy
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
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
Thanks for the suggestion, however StringBuilder will give even better performance. :)
- Pankaj
Yes. I did mean StringBuilder. I tend to get confused between the two very often.
- Bhavya
Its really very easy to understand!! Thanks!!
- rajni
Hi Pankaj, Thank you for the post. Its very clear and easy. What is the ime complexity and of the program?
- Rashmi
There are n! permutations it will take O(n!) time.
- Rudra
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
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
Wow! nice logic thanks for posting. Mozib
- Mozib