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 at every step then permutations of the remaining characters are written next to them one by one.

• 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! * 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 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 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 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 solve this problem. The next step is to make a successful submission of Permutation in String on Code studio.

Frequently asked questions

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!