Home » Interview Questions » String Interview Questions » Write a program to print all permutations of a given string

Write a program to print all permutations of a given string


()

Given a string, write a function that will print all  the permutations of the string

Example

INPUT
s = “ABC”

OUTPUT
ABC, ACB, BAC, BCA, CBA, CAB

Time Complexity : O(n*n!)

Note : There are n! permutations and it requires O(n) time to print a permutation.

Algorithm

Permute()

1. If we picked all elements in the string print teh string. else,

2. For each character in the string

a. Place character in the correct position

     b. permute remaining characters starting from position+1

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
  char temp;
  temp = *x;
  *x = *y;
  *y = temp;
    
}
 
//This function will print all the permutations
//Takes string, starting index and ending index as the arguments
void permute(char *a, int start, int end)
{
  int i;
  if (start == end)
  {  
      cout<<a<<endl;
  }
  else
  {
    for (i = start; i <= end; i++)
    {
      //swap the characters
      swap((a+start), (a+i));
      //recursively call
      permute(a, start+1, end);
      swap((a+start), (a+i)); //backtrack
    }
  }   
}
 

int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}

Try It

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions