New update is available. Click here to update.
sidenav-btnClose
Topic list
Next Greater Number
MEDIUM
15 mins
10 upvotes
Strings
Topics (Covered in this problem)
Problem solved
Skill meter
Strings
-
Other topics
Problem solved
Skill meter
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Trees
-
Graph
-
Dynamic Programming
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

Next Greater Number

Contributed by
Nishant Chitkara
Medium
Avg time to solve 15 mins
Success Rate 90 %
Share
10 upvotes

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.
Detailed explanation ( Input/output format, Notes, Constraints, Images )
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
Reset Code
Full screen
copy-code
Console