Print Permutations - String
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

Question

Print Permutations - String

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

Accepted Answer

Approach :
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.

TC : O(N*N!), where N = length of the String.
SC : O(N)

Accepted Answer

Backtracking

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.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the string.

Because O(N) extra space is required for recursion stack and thus space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N*N!), where N is the length of the String.

In the worst case, there will be N! Recursion calls and for each permutation, it requires O(N) time to print. Thus the overall time complexity will be O(N*N!).

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

Note:

Input Format:

Output Format:

Note:

Constraint:

Top Virtusa Consulting Services Technology Consultant interview questions & answers

Popular interview questions of Technology Consultant

Top HR questions asked in Virtusa Consulting Services Technology Consultant