Problem: Permutations of a String

Given a string STR consisting of lowercase English letters, your task is to return all permutations of the given string in lexicographically increasing order.

Explanation:

A 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]

Question

Problem: Permutations of a String

Given a string STR consisting of lowercase English letters, your task is to return all permutations of the given string in lexicographically increasing order.

Explanation:

A 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[j] = B[j]. Here |A| denotes the length of the string A.

Input:

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 and only line of each test case contains a string STR consisting of lowercase English letters.

Output:

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 on a separate line.

Example:

Input:
1
bca

Output:
abc acb bac bca cab cba

Constraints:

1 ≤ T ≤ 5
1 ≤ |STR| ≤ 9 where |STR| is the length of the string.
Time Limit: 1 sec

Note:

The given string contains unique characters.

Accepted Answer

Return all permutations of a given string in lexicographically increasing order.

Use backtracking to generate all permutations of the string.
Sort the permutations to get them in lexicographically increasing order.
Ensure the string contains unique characters to avoid duplicate permutations.