Problem title
Difficulty
Avg time to solve

Number of rectangles in a grid
Easy
15 mins
Print Parentheses
Easy
10 mins
Find nth elements of spiral matrix
Easy
15 mins
Combination Sum
Easy
15 mins
The N - Queens Puzzle
Moderate
--
LCA In A BST
Moderate
15 mins
Ninja Fight
Easy
10 mins
Next Greater Number
Moderate
15 mins
Hard
45 mins
Binary Numbers
Easy
10 mins 8

# Next Greater Number

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate
90%

Problem Statement

#### You are given a string S which represents a number. You have to find the smallest number strictly greater than the given number which contains the same set of digits as of the original number i.e the frequency of each digit from 0 to 9 should be exactly the same as in the original number.

##### For example:
``````If the given string is 56789, then the next greater number is 56798. Note that although 56790 is also greater than the given number it contains 1 '0' which is not in the original number and also it does not contain the digit '8'.
``````

#### Note:

``````The given string is non-empty.

If the answer does not exist, then return -1.

The given number does not contain any leading zeros.
``````
##### Input Format:
``````The first line of the input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains a string S representing the number.
``````
##### Output Format:
``````The only line of output of each test case should print the number which is just greater than the given number as described above
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= len(S) <= 10^4
Time Limit: 1 sec
``````
##### Sample Input 1:
``````1
1234
``````
##### Sample Output 1:
``````1243
``````
##### Explanation For Sample Input 1:
``````1243 is the next greater number consisting of the same set of digits (1,2,3 and 4)
``````
##### Sample Input 2:
``````2
4321
65312
``````
##### Sample Output 2:
``````-1
65321
``````   Console