Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Example
3.
Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a string?
4.2.
What are the different types of recursions?
4.3.
What is the swap function used in the code and what is the return type of the function?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

C++ Program To Print All Permutations Of A Given String

Author Harsh Goyal
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss the approach of printing all the permutations of a stringBefore jumping on the approach of the problem of printing all the permutations of a given string, let’s first understand what a permutation of a string is,

Permutation : Permutation of string refers to one of the arrangements of all the characters of the string in a manner so that it forms a new string. A string can have N! Number of permutations. 

Problem Statement

We need to print all the permutations of the string provided as input.

Sample Example

Input:

code 

Output:

code, coed, cdoe, cdeo, cedo, ceod,  ocde, oced, odce, odec, oedc, oecd, doce, doec, dcoe, dceo, deco, deoc, eodc, eocd, edoc, edco, ecdo, ecod
Combination Logic

Recommended: Try the Problem yourself first before moving on to the solution

Recommended topic, kth largest element in an array, and Euclid GCD Algorithm

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

Approach

This approach considers checking all the permutations of string and using the backtracking method to backtrack the previous permutations to make another combination.

Steps of Algorithm

Step 1. Call a ‘getResult’ function, which takes three parameters, a string input, the initial index of the substring, and the last index of the substring on which we need to process.

Step 2. In this function, check for the base case, in which if the left index ‘l’ and right index ‘r’ are equal, then print the string and return.

Step 3. If base is not triggered then, make an iteration using a ‘for’ loop and call for each permutation with passing the string after swapping the characters at ‘lth’ and ‘ith’ index of the string and then calling the ‘getResult’ function. 

Step 4. Now again, swap the characters at ‘lth’ and ‘ith’ index of the string ‘input’, which is considered as the backtracking step.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Print all the permutations
void getResult(string input, int l, int r)
{
   // Base case
   if (l == r)
   {
       cout << input << ", ";
       return;
   }
  
   // All combinations
   for (int i = l; i <= r; i++)
   {
       // Swap
       swap(input[l], input[i]);

       // Recursive call
       getResult(input, l + 1 , r);

       // Swap (backtracking)
       swap(input[l], input[i]);
   }
   
   return;
}

int main()
{
   string input = "code";
   int n = input.length();
 
   cout << "All Permutations:- " << endl;
   getResult(input, 0, n - 1);
   return 0;
}

Output:

Output :
All Permutations:- 
code, coed, cdoe, cdeo, cedo, ceod, ocde, oced, odce, odec, oedc, oecd, doce, doec, dcoe, dceo, deco, deoc, eodc, eocd, edoc, edco, ecdo, ecod,

Complexity Analysis

Time Complexity: O(N * N!)

Incall to ‘getResult()’, we are checking all the ‘N!’ number of combinations where ‘N’ is the length of the string, and it takes ‘N’ time to print all the permutations. Therefore the overall time complexity is O(N * N!).

Space Complexity O(R - L)

As we are using extra space of size R - L only, therefore the overall space complexity is O(R - L), where ‘R’ and ‘L’ are the integral indexes that have been passed in each call to the ‘getResult’ function, and ‘R - L’ means the length of the string.

Also check out - Substr C++

 

You should watch this video to know the logic behind this and to understand it better.

Frequently Asked Questions

What is a string?

The string is a data type that is the collection of the characters, and we can traverse the string like an array.

What are the different types of recursions?

There are two types of recursion:- Normal Recursion and Tail Recursion.

What is the swap function used in the code and what is the return type of the function?

‘swap()’ function is an inbuilt function in C++ STL. It is used to swap the variables passed in it. It accepts two mandatory arguments ‘X’ and ‘Y’ which are meant to be swapped. There is no return type of the function, it just swaps the values passed in it.

Conclusion

In this article, we discussed the printing of all permutations of a string and discussed the approach to solve this problem programmatically, the Time and Space Complexity.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Recommended Problems:


Recommended Readings:


Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Count of all unique paths from given source to destination in a Matrix
Next article
Maximize Cost of Forming a Set of Words Using Given Set of Characters
Live masterclass