Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).

Given a string of length n, print all permutation of the given string without Repetition . (Repetition of characters is NOT allowed)

---

Print all the permutations of a string without repetition in Java. lets understand with sample input and output below, 

Case 1
Input: A
Output: A
     
Case 2
Input: AB
Output:

1. AB
2. BA

Case 3
Input:  ABC
Output:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA 

How many permutations is possible:

---

Algorithm

 Lets see how many permutation is possible for given n character String.
 In string "AB", n is 2
 In string "ABC", n is 3

  From above permutations displayed, we can see relation as n!.

 So for "AB", total permutations are 2! = 2.
 For "ABC", total permutations are 3! = 6.

How to print all permutation?

It is very easy, Lets take an example of String "ABC"
 
We will take recursive approach. In this approach important thing is base case.
We will try to make each permutation by adding characters one by one to the temporary 
string  "permutation" that need to be printed and removing the same character one by one 
from original string. As we are removing one by one character from original string and adding it to "permutation" string,   So it is sure at one point length of original String will be 0 and length of 
"permutation" string will be 3.
 
So base case is, when the length of our original string became 0, we will print the string  "permutation" and return.
 
Now, how we will form "permutation" string is, 
remove first character of original string and add it to "permutation" string and check the 
length of original string which is not 0, true, so call function again,

"string" = "BC" "permutation" = "A"
     
remove first character of original string and add it to "permutation" string and check the length of original string which is not 0, true, so call function again,

"string" = "C" "permutation" = "AB"
     
remove remaining character of original string and add it to "permutation" string and check the length of original string which is not 0, false, so it is time to print the string "permutation".

"string" = "" "permutation" = "ABC"
     
1st permutation is ABC

after returning from printing 1st permutation,
      "string" = "C" "permutation" = "AB" 
              Original string has only one character "C" whose permutation is covered, 
              no more permutation possible of one character string, so return,

      "string" = "BC" "permutation" = "A"
               From original string "ABC", we covered permutation keeping 
              "A", "B" at place and changing "C", which gave "ABC" as 1st permutation.
               Now, its time to work on 2nd character of original string

Now, remove second character of original string and add it to "permutation" string and check the 
length of original string which is not 0, true, so call function again,
       "string" = "B" "permutation" = "AC"
     
remove remaining character of original string and add it to "permutation" string and check the length of original string which is not 0, false, so it is time to print the string "permutation".
      "string" = "" "permutation" = "ACB"
     
if we continue the same process in a loop, then we will get all our permutations without repetition of characters.

Stack trace of printing all permutations of a string without duplicates in java

Program to Print all permutations of a string without duplicates in java

package javabypatel;

public class StringPermutationWithoutRepetition {
 
 public static void main(String[] args) {
  permutation("ABC");
 }
 
 private static void permutation(String string) {
  printPermutation(string,"");
 }

 private static void printPermutation(String string, String permutation) {
  
  if(string.length()==0){
   System.out.println(permutation);
   return;
  }
  
  for (int i = 0; i < string.length(); i++) {
   char toAppendToPermutation = string.charAt(i);
   String remaining = string.substring(0, i) + string.substring(i + 1);
   
   printPermutation( remaining,  permutation + toAppendToPermutation);
  }  
 }
}

Time Complexity:

---

Time complexity of program to print all permutations of a string is O(n*n!).

How it comes to (n * n!)
From the above stack trace picture of a program you can see, for printing permutation of string "ABC" i.e. 3 character word, what it does is 

Outer:
Keeping A at place, it finds all the permutations of remaining string, then,
          Inner:
          Keeping B at place, it finds all the permutations of remaining string, then,
                     keeping C at place, it finds all the permutations of remaining string, then,
          Change B to C and find all the permutations of remaining string, then, 
                     ...........
           ...............             
Keeping B at place, it finds all the permutations of remaining string, then,
           ...........
           ...........
Keeping C at place, it finds all the permutations of remaining string.

How many times Outer: label has to print is number of characters present in word.
that is n
How many times Inner: label has to print is number of permutations of a character present in word.
this brings n!
 
Now, if we read this line again,
Keeping Outer character at place, find all permutation of Inner sting, then replace 
Outer character at place, and again find all permutation of Inner sting, and 
so on till end of Outer character.

hence the complexity is O(n * n! )

Another approach that work with duplicates (LeetCode 47. Permutations II)

package javabypatel;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().permuteUnique(new int[] {1,2,1}));
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null) {
            return null;
        }

        List<List<Integer>> res = new ArrayList<>();

        permuteHelper(nums, new boolean[nums.length], new ArrayList<>(), res);
        return res;
    }

    private void permuteHelper(int[] nums, boolean[] visited, List<Integer> temp, List<List<Integer>> res) {
        if (temp.size() == nums.length) {
            if (!res.contains(temp)) {
                res.add(new ArrayList<>(temp));
                return;
            }
        }

        for (int i=0; i<nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                temp.add(nums[i]);
                permuteHelper(nums, visited, temp, res);
                temp.remove(temp.size()-1);
                visited[i] = false;
            }
        }
    }
}
  
  

Another nice way of printing permutations if there are duplicates.

package javabypatel;

import java.util.ArrayList;
import java.util.List;

public class StringPermutationWithoutRepetition {

    public static void main(String[] args) {

        List<Object> list = new ArrayList<Object>();
        list.add("a");
        list.add("b");
        list.add("c");

        int[] countList = new int[] {1, 1, 1};
        Object[] result = new Object[list.size()];

        printPermutations(list, countList, result, 0);
    }

    private static void printPermutations(List<Object> list, int[] countList, Object[] result, int pointer) {
        if (pointer == list.size()) {
            printArray(result);
            return;
        }

        for (int i = 0; i < list.size(); i++) {
            if (countList[i] == 0) {
                continue;
            }

            result[pointer] = list.get(i);
            countList[i] = countList[i] - 1;

            printPermutations(list, countList, result, pointer + 1);

            countList[i] = countList[i] + 1;
        }
    }

    private static void printArray(Object input[]) {
        for (Object ch : input) {
            System.out.print(ch);
        }
        System.out.println();
    }
}

Explanation: https://www.youtube.com/watch?v=nYFd7VHKyWQ

If there are NO duplicates. (Leetcode 46. Permutations)

package javabypatel;
 
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null) {
            return null;
        }

        List<List<Integer>> res = new ArrayList<>();

        permuteHelper(nums, new ArrayList<>(), res);
        return res;
    }

    private void permuteHelper(int[] nums, List<Integer> temp, List<List<Integer>> res) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }

        for (int i=0; i<nums.length; i++) {
            if (!temp.contains(nums[i])) {
                temp.add(nums[i]);
                permuteHelper(nums, temp, res);
                temp.remove(temp.size()-1);
            }
        }
    }
}
  

---

Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).

Print all combinations/permutations of a string of length k that can be formed from a set of n characters.

Print all subsets of a given set.

Enjoy !!!!

If you find any issue in post or face any error while implementing, Please comment.