Permutations of a String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
99 upvotes
Asked in companies
GoogleMakeMyTripDisney + Hotstar

Problem statement

You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1 <= i <= min(|A|, |B|)), that A[i] < B[i], and for any j (1 <= j < i) A[i] = B[i]. Here |A| denotes the length of the string A.

For example :

If the string is “bca”, then its permutations in lexicographically increasing order are { “abc”, “acb”, “bac”, “bca”, “cab”, “cba” }.
Note: 
Given string contains unique characters.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. Then the T test cases follow.

The first line and only line of each test case contains a string 'STR' consisting of lowercase English letters.
Output Format : 
For every test case, the permutations of the given string are printed in lexicographically increasing order separated by space.

The output of each test case is printed in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= |STR| <= 9

Where |STR| is the length of the string.

Time Limit: 1 sec
Sample Input 1:
3
abc
bc
c
Sample Output 1:
abc acb bac bca cab cba
bc cb
c
Explanation for Sample Input 1:
In the 1st test case, there are 6 permutations of the given string.
In the 2nd test case, there are 2 permutations of the given string.
In the 3rd test case, there is only 1 permutation of the given string.
Sample Input 2:
1
xyz
Sample Output 2:
xyz xzy yxz yzx zxy zyx
Hint

Think of using backtracking to generate all permutations.

Approaches (2)
Backtracking

The idea is to fix a character at a position and then find the permutations for rest of the characters.

Make a list ‘ans’ which will contain the permutations of the given string.

 

Algorithm:

Let’s define a function generatePermutaionsHelper(Str, l, r). This function generates the permutations of the substring which starts from index  ‘l’ and ends at index  ‘r’.

  • Call the function: generatePermutaionsHelper(Str, l, r).
  • If ‘l’ is equal to ‘r’, we have found a permutation. Push the string Str in the ‘ans’ list.
  • Else,  iterate on the indices from ‘l’ to ‘r’.
    • Let ‘i’ denote the current index.
    • Fix ‘ith’ character on the index ‘l’, to do this swap Str[l] and Str[i].
    • Call the function for rest of the characters: generatePermutaionsHelper(Str, l + 1, r).
    • Backtrack and swap the character Str[l] and Str[i] again.

Now, we have the list ‘ans’ which contains all the permutations of the given string. To order this in lexicographically increasing order, we will sort the list.

Time Complexity

O(N! * log(N!)), Where N is the length of the given string.
 

There are N! Permutations of a string of length N. In each recursive call, we are traversing the string which will take O(N) time in the worst case. Thus, generating all permutations of a string take O(N * N!) time.
 

We are also sorting the ‘ans’ list of size O(N!) which will take O(N! * log(N!)) time. 
 

Thus, the final time complexity is O(N! * log(N!) + N * N!) ~ O(N! * log(N!))

Space Complexity

O(N * N!), Where N is the length of the given string.
 

O(N) recursion stack is used by the recursive function, we are also storing the permutations in a list which will O(N * N!) space. Thus, the final space complexity is O(N + N * N!) ~ O(N * N!).

Code Solution
(100% EXP penalty)
Permutations of a String
Full screen
Console