Given a string str, the task is to print all the permutations of str. A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement. For instance, the words ‘bat’ and ‘tab’ represents two distinct permutation (or arrangements) of a similar three letter word.
Examples:
Input: str = “cd”
Output: cd dcInput: str = “abb”
Output: abb abb bab bba bab bba
Approach: Write a recursive function that prints every permutation of the given string. Terminating condition will be when the passed string is empty.
Below is the implementation of the above approach:
Java
// Java program to print all the permutations// of the given stringpublic class GFG { // Function to print all the permutations of str static void printPermutn(String str, String ans) { // If string is empty if (str.length() == 0) { System.out.print(ans + " "); return; } for (int i = 0; i < str.length(); i++) { // ith character of str char ch = str.charAt(i); // Rest of the string after excluding // the ith character String ros = str.substring(0, i) + str.substring(i + 1); // Recursive call printPermutn(ros, ans + ch); } } // Driver code public static void main(String[] args) { String s = "abb"; printPermutn(s, ""); }} |
abb abb bab bba bab bba
Time Complexity: O(N2), where N is the length of the given string
Auxiliary Space: O(N)
When the permutations need to be distinct.
Examples:
Input: str = “abb”
Output: abb bab bbaInput: str = “geek”
Output: geek geke gkee egek egke eegk eekg ekge ekeg kgee kege keeg
Approach: Write a recursive function that print distinct permutations. Make a boolean array of size ’26’ which accounts the character being used. If the character has not been used then the recursive call will take place. Otherwise, don’t make any call. Terminating condition will be when the passed string is empty.
Below is the implementation of the above approach:
Java
// Java program to print all the permutations// of the given stringpublic class GFG { // Function to print all the distinct // permutations of str static void printDistinctPermutn(String str, String ans) { // If string is empty if (str.length() == 0) { // print ans System.out.print(ans + " "); return; } // Make a boolean array of size '26' which // stores false by default and make true // at the position which alphabet is being // used boolean alpha[] = new boolean[26]; for (int i = 0; i < str.length(); i++) { // ith character of str char ch = str.charAt(i); // Rest of the string after excluding // the ith character String ros = str.substring(0, i) + str.substring(i + 1); // If the character has not been used // then recursive call will take place. // Otherwise, there will be no recursive // call if (alpha[ch - 'a'] == false) printDistinctPermutn(ros, ans + ch); alpha[ch - 'a'] = true; } } // Driver code public static void main(String[] args) { String s = "geek"; printDistinctPermutn(s, ""); }} |
geek geke gkee egek egke eegk eekg ekge ekeg kgee kege keeg
Time Complexity: O(N2), where N is the length of the given string
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
