Print Permutations

0

0 votes
Recursion
Problem

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.

 

Constraints :

1 <= T <= 5

1 <= |STR| <= 9 Where |STR| is the length of the string. 

Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?