Table of Contents

**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 InputabcSample Outputabc 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
to get the permutation of the rest of the characters.*generatePermutaionsHelper(Str, l + 1, r)*

- 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 caseif (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);// backtrackswap(str[l], str[i]); } } int main() {// stores the permutations of the stringvector<string> ans; string str = "aac"; int l = 0; int r = str.size() - 1;//Empty Input Stringif(str.length()==0) { cout<<"No Permutations Possible!!"; } else generatePermutationsHelper(str, l, r, ans);// lexicographically increasing ordersort(ans.begin(), ans.end()); for(int i = 0;i<ans.size();i++) { cout<<ans[i]<<endl; } return 0; }

**Output:**

aacaacacaacacaacaa

**Time Complexity**

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

**Reason: **

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

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

**Space Complexity**

The time complexity of this approach is **O(N * 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 * N!)** space. Thus, the final space complexity is O(N + N * N!) ~ O(N * 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 emptyif (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 usedbool alpha[26]; for (int i = 0; i < str.length(); i++) { char ch = str.at(i);// the string after excluding the ith characterstring 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// callif (alpha[ch - 'a'] == false) printPermutations(ros, ans + ch); alpha[ch - 'a'] = true; } } int main() { string s = "aabc"; string ans = "";//Empty Input Stringif(s.length()==0) { cout<<"No Permutations Possible!!"; } else printPermutations(s, ans); return 0; }

Output:

aabcaacbabacabcaacabacbabaacbacabcaacaabcabacbaa

**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 ** true** if the rearrangement of the string to a lexicographically greater permutation is possible. Otherwise, it returns

**.**

*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 stringvoid printPermutation(string str) {// Sort the string in ascending ordersort(str.begin(), str.end());// Keep printing next permutationdo { cout << str << endl; } while (next_permutation(str.begin(), str.end())); } int main() { string str = "aabc";// Empty Input Stringif(str.length()==0) { cout<<"No Permutations Possible!!"; } else printPermutation(str); return 0; }

Output:

aabcaacbabacabcaacabacbabaacbacabcaacaabcabacbaa

**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 solve 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.

**What are the permutations in string?**

The different arrangements of all the characters of the string is called permutations in string.

**What is a permutation formula?**

he mathematical formula of permutation is nPr = (n!) / (n-r)!.

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

The time complexity of the backtracking approach to get all the permutations in string is O(N! * log(N!)). Where N is the length of the string.

**Key Takeaways**

The string modification includes a wide variety of problems. This article explained one of those problems, finding all the permutations 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 organisations.

So, keep learning and keep hustling!

## Leave a Reply