Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the permutation of string?
3.
Problem Statement
3.1.
Sample Input
3.2.
Sample Output 
3.3.
Solution Approach
4.
Print Permutations of a given String using Backtracking
5.
Algorithm
6.
Implementation 
6.1.
Output
6.2.
Drawbacks of the above approach
7.
Another approach by concatenating Substrings
7.1.
Output 
8.
Another approach by using itertools package(Python)
8.1.
Output 
9.
Another Approach Using Inbuilt STL Function
9.1.
Output
10.
Frequently asked questions
10.1.
How many permutations can a string have?
10.2.
How do I print all combinations of a string?
10.3.
Which algorithm is best for permutation?
10.4.
What is the formula for permutations of a string?
11.
Conclusion
Last Updated: Mar 27, 2024
Medium

Permutations of given String

Author Pallavi singh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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 permutation of a string is a rearrangement of its characters to create different sequences. It involves changing the order of characters while retaining all the original characters. For example, permutations of "ABC" include "ABC," "ACB," "BAC," "BCA," "CAB," and "CBA." Permutations are often computed recursively or iteratively, generating all possible orders of the characters in the given string. 

permutation of string

What is the permutation of string?

A  Permutation of string is an arrangement of its characters in a particular order. A new string is created by rearranging the characters of the old string. The number of permutations of a string depends on its length and is determined by the factorial of that length. Permutations are frequently employed in algorithms and tasks such as creating all possible combinations, solving riddles, and analyzing various element arrangements.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement

String permutations have applications ranging from security and encryption to optimization and analysis. It allows us to solve complex problems and study varied data configurations. An example of a string permutation is given below. In this example, you have to print all the permutations of the string “abc”. So in the output, you will see all 6 permutations of “abc”.

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.

Print Permutations of a given String 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 the string, backtracking is the most optimal approach. Let’s see with the help of a Recursion tree.

Program to find all the permutations of a string with the help of the 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 

#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. 

Another approach by concatenating Substrings

An alternative approach to finding all permutations of a string is to form each permutation by concatenating substrings of the string, which are generated by removing one character at a time. The base case for the recursive approach would be when the string is empty, at which point we have generated a permutation.

This method can be considered a divide-and-conquer algorithm, as we are "dividing" the problem of generating all permutations into smaller problems of generating permutations of smaller strings.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Function to generate all permutations of a string
vector<string> generate_permutations(string s) {
   // Vector to store all permutations
   vector<string> permutations;
   // Base case: when the string is empty
   if(s.empty()){
       permutations.push_back("");
       return permutations;
   }
   // For every character in string
   for(int i = 0; i < s.size(); i++){
       // Form a string by removing the i'th character
       string remaining = s.substr(0, i) + s.substr(i+1);
       // Generate all permutations for the remaining string
       vector<string> remaining_perms = generate_permutations(remaining);
       // For each permutation of the remaining string
       for(int j = 0; j < remaining_perms.size(); j++){
           // Prepend the current character and append it to permutations
           permutations.push_back(s[i] + remaining_perms[j]);
       }
   }
   // Return all generated permutations
   return permutations;
}
int main() {
   string str = "abc";
   vector<string> permutations = generate_permutations(str);
   // Print all permutations
   for(int i = 0; i < permutations.size(); i++)
       cout << permutations[i] << endl;
   return 0;
}

Output 

abc 
acb
bac
bca
cab
cba

This approach also has a time complexity of O(n!), where n is the length of the string. The factorial time complexity arises from the fact that there are n! Permutations of a string of length n. As such, both of these methods can be slow for large strings. However, this method uses more space than the backtracking approach, as it creates many temporary string objects.

Another approach by using itertools package(Python)

Python's itertools library has a function called permutations() that can be used to generate all permutations of a string concisely and efficiently. Here is an example of how you can use it:

import itertools

def generate_permutations(s):
    # itertools.permutations returns an iterator yielding tuples, so we join each tuple to form strings
    return [''.join(p) for p in itertools.permutations(s)]

def main():
    s = "abc"
    print("All permutations of the string:")
    print(generate_permutations(s))

if __name__ == "__main__":
    main()

Output 

Output

The time and space complexity for generating all permutations of a string using itertools.permutations() in Python is as follows:

Time Complexity: O(n!) - There are n! Permutations of a string of length n, so the time complexity is factorial in the size of the string.

Space Complexity: O(n) - This approach generates each permutation one at a time, so the space complexity is linear in the string size.

However, please note that the space complexity of the generate_permutations(s) function as written is technically O(n*n!) because it creates a list of all the permutations, and each permutation is a string of length n. If you were to yield each permutation one at a time (by making generate_permutations a generator function or by directly iterating over itertools.permutations(s)), you could reduce the space complexity to O(n).

Another Approach Using Inbuilt STL Function

In C++, the Standard Template Library (STL) provides an inbuilt function std::next_permutation to generate a given string or sequence permutations. This function rearranges the elements in the range [first, last) into the next lexicographically greater permutation.

Here is how you can use std::next_permutation to generate all permutations of a string:

#include <iostream>
#include <string>
#include <algorithm>
int main() {
   std::string str = "abc";
   // Sort the string in lexicographically ascending order
   std::sort(str.begin(), str.end());
   // Generate all permutations
   do {
       std::cout << str << std::endl;
   } while(std::next_permutation(str.begin(), str.end()));
   return 0;
}

Output

Output

Time Complexity: The time complexity is O(n!), where n is the size of the string. This is because there are n! Permutations of a string of length n, and each call to std::next_permutation takes O(n) time.

Space Complexity: The space complexity is O(1) because this method generates each permutation in place without using any additional space. The only space used is the input string itself.

Also see, Palindrome string

Frequently asked questions

How many permutations can a string have?

The number of permutations of a string is always equal to the factorial of the length of the string. For example : string HELLO of length 5 has 5! permutations i.e. 120 permutations in total

How do I print all combinations of a string?

We can count the occurrences of all the characters in the string using a map, then using recursion, all the possible combinations can be printed. And lastly, storing the elements and their counts in two different arrays.

Which algorithm is best for permutation?

The best algorithm for generating permutations depends on the context. The `itertools.permutations()` method in Python or `std::next_permutation` in C++ STL is usually more efficient and easier to use due to their ability to generate permutations one at a time, reducing memory usage.

What is the formula for permutations of a string?

The formula for permutations of a string of 'n' distinct characters is 'n!,' where 'n' represents the number of characters, and '!' denotes the factorial of 'n.'

Conclusion

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

Recommended Readings:

Previous article
Subsets (ii)
Next article
Minimize swaps of pairs of characters required such that no two adjacent characters in the string are the same
Live masterclass