Problem

Submissions

Hints & solutions

Discuss

Day 13 : All Possible Permutations - String

Easy

0/40

Average time to solve is 30m

126 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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:

1 <= |S| <= 8

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

Time limit: 1 sec

Sample Input 1:

cba

Sample Output 1:

abc
acb
bac
bca
cab
cba

Explanation for Sample Output 1:

All the possible permutations for string "cba" will be "abc", "acb", "bac", "bca", "cab" and "cba".

Sample Input 2:

xyx

Sample Output 2:

xyx
xxy
yxx
yxx
xyx
xxy

Explanation for Sample Output 2:

All the possible permutations for string "xyx" will be "xyx", "xxy", "yxx", "yxx", "xyx" and "xxy". Here, all three permutations "xyx", "yxx", "xxy" are repeating twice but we need to print all the possible permutations and hence we are printing them twice..

Hint 1

Think about how you can break this problem between the first character of the string and the rest of it.

Approaches (1)

Approach 1

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.

Time Complexity

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!).

Space Complexity

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).

(100% EXP penalty)

Day 13 : All Possible Permutations - String

Console