Question 9 : Write a program to print all permutations of String in java?

 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:  

public class CloudTechtwitter {
 
    static void printPermutn(String str, String ans)
    {
 
        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, "");
    }
}

Python code 

def print_permutations(s, ans=""):
    if len(s) == 0:
        print(ans, end=" ")
        return
    for i in range(len(s)):
        ch = s[i]
        ros = s[:i] + s[i+1:]
        print_permutations(ros, ans + ch)


print_permutations("abb")

Approach: Write a recursive function that prints distinct permutations. Make a boolean array of size ’26’ which accounts for the character being used. If the character has not been used then the recursive call will take place. 

Otherwise, don’t make any calls. The termination condition will be when the passed string is empty.

Below is the implementation of the above approach:

public class CloudTechTwitter {

    // Function to print all distinct permutations of str
    static void printDistinctPermutations(String str, String ans) {
        if (str.isEmpty()) {
            System.out.print(ans + " ");
            return;
        }

        boolean[] used = new boolean[26]; // To track used characters

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            String remaining = str.substring(0, i) + str.substring(i + 1);

            if (!used[ch - 'a']) {
                printDistinctPermutations(remaining, ans + ch);
                used[ch - 'a'] = true;
            }
        }
    }

    public static void main(String[] args) {
        String s = "abba";
        printDistinctPermutations(s, "");
    }
}

without recursion 

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Permutations {
    // Function to print all distinct permutations of str
    static void printDistinctPermutations(String str) {
        if (str == null || str.length() == 0) {
            return;
        }

        // Queue to store permutations
        Queue<String> permutations = new LinkedList<>();
        // Set to store distinct permutations
        Set<String> distinctPermutations = new HashSet<>();

        // Initialize the queue with the first character
        permutations.add("");

        // Process each character of the string
        for (char currentChar : str.toCharArray()) {
            int size = permutations.size();

            // Generate new permutations by inserting the current character
            // into all positions of existing permutations
            while (size-- > 0) {
                String perm = permutations.poll();
                for (int k = 0; k <= perm.length(); k++) {
                    String newPerm = perm.substring(0, k) + currentChar + perm.substring(k);
                    if (newPerm.length() == str.length()) {
                        distinctPermutations.add(newPerm);
                    } else {
                        permutations.add(newPerm);
                    }
                }
            }
        }

        // Print all distinct permutations
        for (String perm : distinctPermutations) {
            System.out.print(perm + " ");
        }
    }

    public static void main(String[] args) {
        String s = "abba";
        printDistinctPermutations(s);
    }
}

Final Comparison

Approach	Time Complexity	Space Complexity	Best Use
Recursive swapping or substring recursion	O(n × n!)	O(n)	⭐ Best generic solution; classic
Distinct permutations using boolean array	O(n × n!)	O(n)	Best when duplicates should be omitted
Iterative using queue / set	O(n × n!)	O(n!)	Useful for distinct permutations (non-recursive)