Permutations of a String
You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1

Question

Permutations of a String

You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1 <= i <= min(|A|, |B|)), that A[i] < B[i], and for any j (1 <= j < i) A[i] = B[i]. Here |A| denotes the length of the string A.

For example :

If the string is “bca”, then its permutations in lexicographically increasing order are { “abc”, “acb”, “bac”, “bca”, “cab”, “cba” }.

Note:

Given string contains unique characters.

Input Format :

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. Then the T test cases follow.

The first line and only line of each test case contains a string 'STR' consisting of lowercase English letters.

Output Format :

For every test case, the permutations of the given string are printed in lexicographically increasing order separated by space.

The output of each test case is printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= |STR| <= 9

Where |STR| is the length of the string.

Time Limit: 1 sec

Accepted Answer

Backtracking

The idea is to fix a character at a position and then find the permutations for rest of the characters.

Make a list ‘ans’ which will contain the permutations of the given string.

Algorithm:

Let’s define a function generatePermutaionsHelper(Str, l, r). This function generates the permutations of the substring which starts from index ‘l’ and ends at index ‘r’.

Call the function: generatePermutaionsHelper(Str, l, r).
If ‘l’ is equal to ‘r’, we have found a permutation. Push the string Str in the ‘ans’ list.
Else, iterate on the indices from ‘l’ to ‘r’.
- Let ‘i’ denote the current index.
- Fix ‘ith’ character on the index ‘l’, to do this swap Str[l] and Str[i].
- Call the function for rest of the characters: generatePermutaionsHelper(Str, l + 1, r).
- Backtrack and swap the character Str[l] and Str[i] again.

Now, we have the list ‘ans’ which contains all the permutations of the given string. To order this in lexicographically increasing order, we will sort the list.

Space Complexity: OtherExplanation:

O(N * N!), Where N is the length of the given string.

O(N) recursion stack is used by the recursive function, we are also storing the permutations in a list which will O(N * N!) space. Thus, the final space complexity is O(N + N * N!) ~ O(N * N!).

Time Complexity: OtherExplanation:

O(N! * log(N!)), Where N is the length of the given string.

There are N! Permutations of a string of length N. In each recursive call, we are traversing the string which will take O(N) time in the worst case. 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!))

Java (SE 1.8)

/*

    Time Complexity: O(N! * log(N!))

    Space complexity: O(N * N!)

    

    Where N is the length of the given string.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution 

{   

    public static String tempStr;

    

    public static void swap(String str, int i , int j)

    {

        StringBuilder sb = new StringBuilder(str);

        sb.setCharAt(i, str.charAt(j));

        sb.setCharAt(j, str.charAt(i));

        tempStr = sb.toString();

    }

    

    public static void generatePermutationsHelper(String str, int l, int r, ArrayList ans)

    {

        // Base case

        if (l == r)

        {

            ans.add(str);

            return;

        }

        for (int i = l; i <= r; i++)

        {   

            swap(str, l, i);

            str = tempStr;

            

            generatePermutationsHelper(str, l + 1, r, ans);

            

            // Backtrack

            swap(str, l, i);

            str = tempStr;

        }

    }



    public static ArrayList generatePermutations(String str) 

    {

        // Stores the permutations of the string

        ArrayList ans = new ArrayList<>();



        int l = 0;

        int r = str.length() - 1;



        // Call the recursive function

        generatePermutationsHelper(str, l, r, ans);



        // Lexicographically increasing order

        Collections.sort(ans);



        return ans;

    }

}

C++ (g++ 5.4)

/*
    Time Complexity: O(N! * log(N!))
    Space complexity: O(N * N!)
    
    Where N is the length of the given string.
*/

#include 

void generatePermutationsHelper(string &str, int l, int r, vector &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]);
    }
}

vector generatePermutations(string &str)
{
    // stores the permutations of the string
    vector ans;

    int l = 0;
    int r = str.size() - 1;

    // call the recursive function
    generatePermutationsHelper(str, l, r, ans);

    // lexicographically increasing order
    sort(ans.begin(), ans.end());

    return ans;
}

Python (3.5)

'''

    Time Complexity: O(N! * log(N!))

    Space complexity: O(N * N!)

    

    Where N is the length of the given string.

'''





def generatePermutationsHelper(str, l, r, ans):



    # base case

    if (l == r):

        ans.append(str)

        return



    for i in range(l, r + 1):

        # Swapping the characters at position i and l

        str = list(str)

        str[l], str[i] = str[i], str[l]

        str = "".join(str)



        generatePermutationsHelper(str, l + 1, r, ans)



        # backtrack

        str = list(str)

        str[l], str[i] = str[i], str[l]

        str = "".join(str)





def generatePermutations(str):



    # stores the permutations of the string

    ans = []



    l = 0

    r = len(str) - 1



    # call the recursive function

    generatePermutationsHelper(str, l, r, ans)



    # lexicographically increasing order

    ans.sort()



    return ans

Accepted Answer

Optimised Approach

In this approach, we will generate the permutations in increasing order. The first permutation will be the string sorted in increasing order and the last permutation will be the string sorted in decreasing order.

Make a list ‘ans’ which will contain the permutations of the given string.

Algorithm:

Sort the given string and add this to the ‘ans’ list. This will be the first permutation.
Now we will generate the next higher permutations until there is no next higher permutation possible.

Take the previous permutation as the current string.
Find the rightmost character in the string, which is smaller than its next character. Let’s call this character ‘first’.
If there is no such character it means we have found all the permutations.
Else, find the smallest character on the right of the ‘first’ character which is greater than the first. Let’s call this character ‘second’.
Swap ‘first’ and ‘second’.
Sort the substring after the original index of ‘first’ character to end (the substring after the original index of ‘first’ character will be in decreasing order, so instead of sorting it in increasing order, we can reverse the substring).
We have found a permutation, add this in the ‘ans’ list.
Repeat steps 1 to 7.

Space Complexity: OtherExplanation:

O(N * N!), Where N is the length of the given string.

We are storing the permutations in a list which will O(N * N!) space. Thus, the final space complexity is O(N * N!).

Time Complexity: OtherExplanation:

O(N * N!), Where N is the length of the given string.

There are N! Permutations of a string of length N. While generating a permutation, we are reversing the string which will take O(N) time in the worst case. Thus, generating all permutations of a string take O(N * N!) time. Also, we are sorting the initial input string, which takes O(N * log(N)) time. Thus, the final time complexity is O((N * log(N) + (N * N!)) = O(N * N!).

C++ (g++ 5.4)

/*
    Time Complexity: O(N * N!)
    Space complexity: O(N * N!)
    
    Where N is the length of the given string.
*/

#include 

vector generatePermutations(string &str)
{
    // stores the permutations of the string
    vector ans;

    sort(str.begin(), str.end());

    while (true)
    {
        ans.push_back(str);

        int first = -1;
        for (int i = str.size() - 2; i >= 0; i--)
        {
            if (str[i] < str[i + 1])
            {
                first = i;
                break;
            }
        }

        if (first == -1)
        {
            // we have found all the permutations
            break;
        }

        int second = first + 1;
        for (int i = first + 2; i < str.size(); i++)
        {
            if (str[i] > str[first] && str[i] < str[second])
            {
                second = i;
            }
        }

        swap(str[first], str[second]);

        // reverse(sort) the substring after index first
        reverse(str.begin() + first + 1, str.end());
    }

    return ans;
}

Java (SE 1.8)

/*

    Time Complexity: O(N * N!)

    Space complexity: O(N * N!)

    

    Where N is the length of the given string.

*/



import java.util.ArrayList;

import java.util.Collections;

import java.util.Arrays;



public class Solution 

{   

	public static String tempStr;

	public static void sort(String str)

    {

        char tempArray[] = str.toCharArray();

        Arrays.sort(tempArray);

        tempStr = new String(tempArray);

    }



	public static void swap(String str, int i , int j)

    {

        StringBuilder sb = new StringBuilder(str);

        sb.setCharAt(i, str.charAt(j));

        sb.setCharAt(j, str.charAt(i));

        tempStr = sb.toString();

    }



	public static ArrayList generatePermutations(String str) 

	{

		// Stores the permutations of the string

		ArrayList ans = new ArrayList<>();



		sort(str);

		str = tempStr;



		while (true) 

		{

			ans.add(str);



			int first = -1;

			for (int i = str.length() - 2; i >= 0; i--) 

			{

				if (str.charAt(i) < str.charAt(i+1)) 

				{

					first = i;

					break;

				}

			}



			if (first == -1) 

			{

				// we have found all the permutations

				break;

			}



			int second = first + 1;

			for (int i = first + 2; i < str.length(); i++) 

			{

				if ((str.charAt(i) > str.charAt(first)) && (str.charAt(i) < str.charAt(second))) 

				{

					second = i;

				}

			}



			swap(str, first, second);

			str = tempStr;

            

            // reverse(sort) the substring after index first

			ArrayList temp = new ArrayList();

            for (int k=first+1 ; k			{

                temp.add(str.charAt(k));

            }

            Collections.reverse(temp);

            String builder = "";

			for(int k = 0 ; k<=first ; k++)

			{

				builder += (str.charAt(k));

			}

            for (Character c: temp) 

			{

                builder += (c);

            }

            str = builder;

		}

		

		return ans;

	}

}

Python (3.5)

'''

    Time Complexity: O(N * N!)

    Space complexity: O(N * N!)

    

    Where N is the length of the given string.

'''





def generatePermutations(str):



    # stores the permutations of the string

    ans = []

    str = sorted(str)

    str = "".join(str)



    while (True):

        ans.append(str)



        first = -1

        for i in range(len(str) - 2, -1, -1):



            if (str[i] < str[i + 1]):

                first = i

                break



        if (first == -1):

            # we have found all the permutations

            break



        second = first + 1

        for i in range(first + 2, len(str)):



            if (str[i] > str[first] and str[i] < str[second]):

                second = i



        str = list(str)

        str[first], str[second] = str[second], str[first]

        str = "".join(str)



        # reverse(sort) the substring after index first

        reversedStr = ''.join(reversed(str[first + 1:]))

        str = str[:first + 1] + reversedStr



    return ans

You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1 <= i <= min(|A|, |B|)), that A[i] < B[i], and for any j (1 <= j < i) A[i] = B[i]. Here |A| denotes the length of the string A.

For example :

Note:

Input Format :

Output Format :

Note :

Constraints :

Algorithm:...read more

Top Vinove Software & Services Network Security interview questions & answers

Popular interview questions of Network Security