# Permutations of a String

Posted: 24 Dec, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
`````` Approach 1

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.