# Print all Permutations in String

**Introduction**

Permutations are typically believed to be a mathematical topic, although this is not true. Mathematics is important in computer science because it teaches us how to communicate abstractly, work with algorithms, self-analyze our computational thinking, and represent real-world solutions accurately.

A substantial level of mathematical knowledge and expertise is required in computer science. So, let’s start by learning about permutations first.

**What are permutations? ***“The different arrangements made out of a given number of things by taking some or all of them is called permutation”.***Example: **The permutation of three letters abc taken two at a time are: ab, ba, bc, cb, ac, ca.

Questions on strings are prevalent in coding competitions and various placements exams. In this article, we will be covering one of the most asked questions based on Strings, **“****Permutations in String****”**

**Problem Statement**

**You are given a string ‘str’ consisting of lowercase letters. Your task is to return all permutations in string in any order.**

**Sample Input**

abc

**Sample Output **

abc acb bac bca cab cba**Solution Approach**

There are various algorithms and techniques to print all the permutations of a string. Some of the optimal ones are explained below.

**Approach-1 Using Backtracking**

Backtracking is an algorithmic strategy for recursively solving problems by attempting to develop a solution gradually, one step at a time, and discarding any solutions that do not satisfy the problem's criteria at any point in time.

To print all the permutations in string, backtracking is the most optimal approach. Let’s see with the help of a recursion tree.

Explanation of the above diagram

- We’ll fix one character

- Next, we’ll fix two characters and so on. These steps are followed by writing the permutation of the remaining characters next to the fixed characters.

**Algorithm:**

We’ll define a function **generatePermutaionsHelper(Str, l, r)**. This function will generate the permutations of the substring starting from index “**l**” and ending at index “**r**”.

- Calling the above function,
**generatePermutaionsHelper(Str, l, r)**.

- If “
**l**” is equal to “**r**”, a new permutation is found. Insert this string in the**“ans”**list.

- Else, continue to iterate on the string from “
**l**” to“**r**”.

- Let
**“i”**denote the current index.

- Swap
**Str[ l ]**and**Str[ i ]**to fix the “ith” character on the index**”l”**.

- Call
**generatePermutaionsHelper(Str, l + 1, r)**to get the permutation of the rest of the characters.

- Now, backtrack and swap
**Str[ l ]**and**Str[ i ]**again.

In the end, we’ll have the list **“ans”** having all the permutations of the given string. If we want the permutations in lexicographically increasing order, we have to sort the list.

**Implementation of Approach-1:**

```
#include <bits/stdc++.h>
using namespace std;
void generatePermutationsHelper(string &str, int l, int r, vector<string> &ans)
{
// base case
if (l == r)
{
ans.push_back(str);
return;
}
for (int i = l; i <= r; i++)
{
swap(str[l], str[i]);
generatePermutationsHelper(str, l + 1, r, ans);
// backtrack
swap(str[l], str[i]);
}
}
int main()
{
// stores the permutations of the string
vector<string> ans;
string str = "aac";
int l = 0;
int r = str.size() - 1;
//Empty Input String
if(str.length()==0)
{
cout<<"No Permutations Possible!!";
}
else
generatePermutationsHelper(str, l, r, ans);
// lexicographically increasing order
sort(ans.begin(), ans.end());
for(int i = 0;i<ans.size();i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
```

**Output:**

```
aac
aac
aca
aca
caa
caa
```

**Time Complexity**

The time complexity of this approach is **O(N!),** where N is the length of the string.

**Reason: **

The reason is there are n! permutations and we are generating them one by one. Thus, generating all permutations of a string takes O(N!) time. We are also sorting the **“ans”** list of size O(N!), which will take O(log(N!)) time.

Thus, the final time complexity is O(log(N!) + N!) ~ O(N!).

**Space Complexity**

The time complexity of this approach is **O(N!)**, Where N is the length of the given string.

**Reason:**

The recursive function uses the **O(N)** recursion stack. We also store the permutations in a list that occupies **O(N!)** space. Thus, the final space complexity is O(N + N!) ~ O(N!).

**Drawbacks of the above approach:**

The above approach works fine when all the characters of a string are unique. But if the string has repeated characters this approach will print duplicate permutations as you saw in the above example.

There is a variation of the backtracking approach(mentioned below) to handle the above test case.

**Approach-2 Avoid Repetition Using Backtracking**

We simply change the above code a little to achieve this. Before calling the subproblems, we must ensure that no character is chosen twice for the prefix.

This basically means that only distinct characters should be chosen at each stage of the recursion. So, how do we go about doing that?

We can accomplish this by creating a boolean array of size (26) to account for the characters being used.

- The recursive function will be called only if the character is not used.
- No character will be chosen more than once. As a result, the distinct selection requirement is met.

A significant advantage of selecting the input string character in this manner is that the permutations generated in the output will be in lexicographical order (dictionary order). This makes it simple to validate the program's correctness.

**Implementation of approach-2:**

```
#include<bits/stdc++.h>
using namespace std;
void printPermutations(string str, string ans)
{
// If string is empty
if (str.length() == 0)
{
cout<<ans<<endl;
return;
}
// Make a boolean array of size '26' which stores true
// at the position in which alphabet is being used
bool alpha[26];
for (int i = 0; i < str.length(); i++) {
char ch = str.at(i);
// the string after excluding the ith character
string ros;
ros = str.substr(0, i) + str.substr(i + 1);
// If the character has not been used
// then a recursive call will take place.
// Otherwise, there will be no recursive
// call
if (alpha[ch - 'a'] == false)
printPermutations(ros, ans + ch);
alpha[ch - 'a'] = true;
}
}
int main()
{
string s = "aabc";
string ans = "";
//Empty Input String
if(s.length()==0)
{
cout<<"No Permutations Possible!!";
}
else
printPermutations(s, ans);
return 0;
}
```

**Output:**

```
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
```

**Time and Space complexity:**

The time complexity is the same as the above approach.

*Have you already noticed a difference in the outputs of two codes even when the input string "aac" is the same?*

**Output 1:** Shows repetitive permutations of a string.

**Output 2:** Yes, it is free of repetitive string permutations.

**Note:** We used a vector to store all the permutations in string in the above approach. Vectors in C++ allow duplicate elements. But, this is not the case with C++ sets. So, no duplicate permutations will be printed if we use a C++ set to store the permutations instead of the vector.

**Approach-3 (Using next_permutation method of c++ library)**

The standard c++ library provides various methods to modify strings- next_permutation is one of them. The ** next_permutation** returns

*if the rearrangement of the string to a lexicographically greater permutation is possible. Otherwise, it returns*

**true***.*

**false**As a result, this method also avoids repetitive permutations in string.

**Implementation of approach-3:**

```
#include <bits/stdc++.h>
using namespace std;
// Function to print permutations of a string
void printPermutation(string str)
{
// Sort the string in ascending order
sort(str.begin(), str.end());
// Keep printing next permutation
do
{
cout << str << endl;
}
while (next_permutation(str.begin(), str.end()));
}
int main()
{
string str = "aabc";
// Empty Input String
if(str.length()==0)
{
cout<<"No Permutations Possible!!";
}
else
printPermutation(str);
return 0;
}
```

**Output:**

```
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
```

**Time complexity:**

The time complexity of this approach is O(N * N!).

**Reason:**

The time complexity of the next_permutation function is O(N). The call to this method is made N! Times. Hence, the total time complexity is O(N * N!).

**Space Complexity**

The space complexity of this approach is **O(N!)**, Where N is the length of the given string.

**Reason:**

No extra space is used in this approach. That’s why it has constant space complexity.

Now, we have discussed all the important approaches to solving this problem. The next step is to make a successful submission of __Permutation in String__ on Code Studio.

## Frequently asked questions

**How many permutations can a string have?**

A string of length n can have factorial n(i.e. n!) possible permutations at maximum. These permutations can be found by rearranging the letters of the string to create a n-length string.

**What are the permutations in a string?**

The different arrangements of all the characters of the string are called permutations in string. Two strings are said to be permutations of each other if they contain the same set of characters and the count of each letter in both strings must be the same. "Abcd" and "dabc," for instance, are permutations of one another.

**What is a permutation formula?**

The mathematical formula of permutation is nPr = (n!) / (n-r)!. A permutation is an arrangement of objects in a definite order. Different permutations can be generated by changing the sequence of these objects in a linear fashion. For example, “abcd” and “acbd” are permutations because here the sequence of a, b, c, and d are changed.

**What is the time complexity of the backtracking approach to get all the permutations in a string?**

The time complexity of the backtracking approach to get all the permutations in the string is O(N!). Where N is the length of the string. The reason is there are n! permutations and we are generating them one by one. Thus, generating all permutations of a string takes O(N!) time. We are also sorting the **“ans”** list of size O(N!), which will take O(log(N!)) time. So, the overall time complexity is O(N!).

**How do I print all combinations of a string?**

All combinations of a string can be generated using the following code:

```
Set getCombinations(String instr, StringBuffer outstr, int index)
{
Set combinations = new HashSet();
for (int i = index; i < instr.length(); i++)
{
outstr.append(instr.charAt(i));
combinations.add(outstr.toString());
combinations.addAll(getCombinations(instr, outstr, i + 1));
outstr.deleteCharAt(outstr.length() – 1);
}
return combinations;
}
```

**How do you find the permutation of a string?**

Different permutations of a string can be generated using various approaches as discussed in the blog. Using backtracking, we can generate permutations of a string in O(N!) time complexity. We can also the in-built method of C++ STL to generate all permutations of a string.

**Conclusion**

The string modification includes a wide variety of problems. This article explained one of those problems, finding all the permutation in string. Basic knowledge of the C++ standard template library and strings is required.

It would be best if you learned more about other top Standard Algorithms for a Coding Interview.

Additionally, you can use CodeStudio to practice a wide range of DSA tasks typically asked in interview rounds. This will assist you in mastering efficient coding methodologies, with the added benefit of scholar interview experiences in large product-based organizations.

So, keep learning and keep hustling!