Last Updated: 24 Dec, 2020

Permutations of a String

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In this approach, we will generate the permutations in increasing order. The first permutation will be the string sorted in increasing order and the last permutation will be the string sorted in decreasing order.

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

Algorithm:

Sort the given string and add this to the ‘ans’ list. This will be the first permutation.
Now we will generate the next higher permutations until there is no next higher permutation possible.

Take the previous permutation as the current string.
Find the rightmost character in the string, which is smaller than its next character. Let’s call this character ‘first’.
If there is no such character it means we have found all the permutations.
Else, find the smallest character on the right of the ‘first’ character which is greater than the first. Let’s call this character ‘second’.
Swap ‘first’ and ‘second’.
Sort the substring after the original index of ‘first’ character to end (the substring after the original index of ‘first’ character will be in decreasing order, so instead of sorting it in increasing order, we can reverse the substring).
We have found a permutation, add this in the ‘ans’ list.
Repeat steps 1 to 7.

Solve now