Permutations of a Given String Using STL

Difficulty Level Medium
Frequently asked in Amazon Apple ByteDance eBay Facebook Google Microsoft Oracle
Permutation STL StringViews 2169

Problem Statement

In the “Permutations of a Given String Using STL” problem, we have given a string “s”. Print all the permutations of the input string using STL functions.

Input Format

The first and only one line containing a string “s”.

Output Format

Print all the permutation of the given string where every line containing only one string.

Constraints

  •  1<=|s|<=10
  • s[i] must be a lower case English alphabet

Example

ABC
ABC
ACB
BCA
BAC
CAB
CBA

Explanation: Here there are total 3*2*1 permutations. After performing operations, we get ABC, ACB, BCA, BAC, CAB, CBA as our answer.

Algorithm for Permutations of a Given String Using STL

Permutation also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation. Here we use the next_permute() function, which rearranges the given string and returns the lexicographically next permutation.

The “rotate()” function rotates elements of a vector/string such that the passed middle element becomes first. For example, if we call rotate for “abc” with the middle as the second element, the string becomes “bca”. And if we again call rotate with the middle as the second element, the string becomes “cab”.

  • Take input string s from the user and another empty string ans.
  • When the size of str becomes 0, ans has a permutation (length of “ans” is n).
  • One by one move all characters at the beginning of the string “ans”.
  • Remove the first character from str and add it to “ans”.
  • Rotate string by one char left.

Implementation

C++ Program for Permutations of a Given String Using STL

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


void permute(string s, string ans)
{
  if(s.size()==0)
  {
    cout<<ans<<endl;
    return;
  }
  for(int i=0;i<s.size();i++)
  {
    permute(s.substr(1),ans+s[0]);
    rotate(s.begin(),s.begin()+1,s.end());
  }
}

int main()
{
  string s;
  cin>>s;
  permute(s,"");
  return 0;
}

Java Program for Permutations of a Given String Using STL

import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static String leftrotate(String str)
    {
            String ans = str.substring(1) + str.substring(0, 1);
            return ans;
    }
    public static void permute(String s, String ans)
    {
            if(s.length()==0)
            {
                    System.out.println(ans);
                    return;
            }
            for(int i=0;i<s.length();i++)
            {
                    permute(s.substring(1),ans+s.charAt(0));
                    s = leftrotate(s);
            }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        permute(s,"");
    }
}





cup
cup
cpu
upc
ucp
pcu
puc

Complexity Analysis for Permutations of a Given String Using STL

Time Complexity

O(n!) where n is the size of the given string. Here we print all the permutation of the given string “s”.

Space Complexity

O(n) where n is the size of the given string. We use this space to store a string that represents a  particular permutation before printing it.

Translate »