Permutations Of A String — Asked in Google and Barclays Interviews

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

Sample Input :

str = “abc”

Sample Output :

abc, acb, bac, bca, cab, cba

Explanation of given Test Cases :

There are 6 permutations of the given string which are { “abc”, “acb”, “bac”, “bca”, “cab”, “cba” }.

Approach :

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:

1. If the size of ‘PERMLIST’ is equal to the size of ‘STR_ARR’.

• Add this permutation in ‘RES’.

2. 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)
Space complexity: O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.