Print Permutations - String

Posted: 23 Sep, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an input string 'S'. Your task is to find and return all possible permutations of the input string.

Note:
1. The input string may contain the same characters, so there will also be the same permutations.

2. The order of permutation does not matter.
Input Format:
The first and only line of input contains a string 'S' of alphabets in lower case characters.
Output Format:
Print all the permutations of the given string 'S' in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.    
Constraint:
0 <= |S| <= 8

Where |S| denotes the length of string 'S'.

Time limit: 1 sec
Approach 1

We can find all the permutations by Backtracking.

 

1: Fix a character then swap all the rest of the remaining character with a fixed character.

2: Then find all permutations for all remaining characters by the recursive call.

3: The base case for the recursion will be when there is only one character left unprocessed.

 

Below is the illustration to approach.

 

Try Problem