Permutations Of A String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
18 upvotes
Asked in companies
BarclaysOYOGoogle inc

Problem statement

Ninja has been given a string ‘STR’ consisting of lowercase English letters. ‘STR’ might contain duplicate characters too. Ninja has to return all unique permutations of the given string in lexicographically increasing order.

Can you help Ninjas to do this task?.

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

For example : 
If the string is “aab”, then its unique permutations in lexicographically increasing order are { “aab”, “aba”, “baa” }.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line and only line of each test case contain 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

Time Limit: 1 second
Sample Input 1:
2 
aa
abc
Sample Output 1:
aa
abc acb bac bca cab cba

Explanation For Sample Output 1:

In the 1st test case, there is only 1 permutation of the given string that is possible i.e { “aa” }.

In the 2nd test case, there are 6 permutations of the given string which are  { “abc”, “acb”, “bac”, “bca”, “cab”, “cba” }.
Sample Input 2:
2 
bcb
acaa
Sample Output 2:
bbc bcb cbb
aaac aaca acaa caaa
Hint

Think of using backtracking to generate all permutations.

Approaches (1)
Backtracking

Our main task in this problem is to handle duplicates. So we can use an extra boolean array/list, ‘USED’, which indicates whether the value is added in our resultant list/vector ‘PERM_LIST’ or not. First, we sort the given input ‘STR’ to make sure we can skip the same characters. When a character is the same as the previous, we can use it only if the last character is not used.

 

 

Approach: 

 

  • We declare a boolean array ‘USED’ which indicates whether the character ‘STR[i]’ is added in our resultant list/vector ‘PERM_LIST’ or not.
  • We declare a list/vector ‘RES’ in which we store all the permutations of the ‘STR’.
  • We call a helper function ‘uniquePremHelper(‘STR_ARR’, ‘USED’, ‘PREM_LIST’, ‘RES’)’.
  • Finally, return ‘RES’.

   uniquePremHelper(‘STR_ARR’, ’USED’, ‘PREM_LIST’, ‘RES’) function is explained below:

  • If the size of ‘PERMLIST’ is equal to the size of ‘STR_ARR’.
    • Add this permutation in ‘RES’.
  • We run a loop while ‘i’ = 0 to ‘STR_ARR.length’
    • If ‘USED[i]’ is true :
      • Continue
    • If the ‘STR_ARR[‘i’]’ and ‘STR_ARR[‘i’ - 1]’ are the same and the previous character is not used.
      • Continue
    • ‘USED[i]’ = true.
    • Add ‘STR_ARR[‘i’]’  in ‘PERM_LIST’.
    • Call uniquePremHelper(‘STR_ARR’, ’USED’, ‘PERM_LIST’)
    • ‘USED[i]’ = false
    • Remove the last element of ‘PERM_LIST’.
Time Complexity

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

 

 

For any recursive function, the time complexity is O(branches ^ depth) * amount of work at each node in the recursive call tree. In this case, we have N * (N-1) * (N-2) * (N-3) * ... * 1= N! branches at each level ‘N’. So the total recursive calls are O(N!)

 

We do N-amount of work in each node of the recursive call tree:

(a) the for-loop and (b) at each leaf when we add ‘N’ elements to a ‘PERM_LIST’. So this is a total of O(N) additional work per node.

 

Therefore, the worst-case time complexity is O(N! * N).

Space Complexity

O(N!), Where N is the length of the given string ‘STR’.

 

 

O(N) recursion stack is used by the recursive function. We are storing the permutations in a list/vector ‘PERM_LIST’of size ‘N’ which takes O(N) space. We are also using a ‘USED’ array/list of size ‘N’  which indicates whether the ‘STR[i]’ is added in our resultant list/vector ‘PERM_LIST’ or not. 

 

Thus, the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Permutations Of A String
Full screen
Console