Permutations Of A String
Last Updated: 23 Feb, 2021
Difficulty: Moderate
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” }.
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
Approach 1
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’.
- If ‘USED[i]’ is true :
