Next Greater Element III

Bob needs to find a permutation of the digits of Alice’s number such that it is greater than Alice’s number but is smallest among all the other permutations greater than that of Alice’s number. 

So we can convert the number into a string and find all possible permutations of the string. Among all the permutations, we need to find the minimum string greater than that of Alice’s number.

Algorithm: 

• Convert the number ‘N’ to a string ‘S’.
• Initialize a string ‘ans’ to “-1”.
• Generate all possible permutations of string ‘S’
  • If the current permutation is greater than ‘S’
    • If ‘ans’ is “-1”, then assign ‘ans’ to the current permutation.
    • Else update ‘ans’ to a minimum of ‘ans’ and current permutation.
• Convert the string ‘ans’ to an integer ‘res’
• Return the ‘res’

We need to find the next permutation lexicographically of the digits of Alice’s number.

Some key observations are :

• If the digits are already sorted in decreasing order, then no such next permutation exists. For e.g., 5521.
• If the digits are sorted in ascending order, then swap the last two distinct digits. For example, let’s take the number 1234, then its next permutation will be 1243.
• For other numbers, we need to try to make changes towards the rightmost side so that the resulting permutation is as small as possible. To understand this, let’s try to find the next permutation of 23576.
  • Let’s focus on the last two digits, i.e. 76. Since it’s already in decreasing order, we won’t get any permutation greater than this.
  • Now let’s focus on the last three digits, i.e. 576. We can replace 5 with 6 or 7 to get a higher number. Since we want the smallest possible, we will replace 5 with 6. We know 6_ _ will always be greater than 5_ _, so we put the rest of the digits in ascending order so that we get the smallest possible with is 657. So the final answer will be 23657.

So, we can iterate in reverse order storing the maximum digit, and once we find a digit that is smaller than the maximum digit, we need to swap that digit with the smallest digit that is towards the right side and is greater than that digit. In the end, we need to sort the rest of the elements towards the right. For example, 23576, we can swap 5 and 6 to get 23675 and then sort the remaining elements towards the right to get 23657.

Algorithm: 

• Convert the number ‘N’ to a string ‘S’.
• Initialize a char ‘mx’ to ‘0’
• Iterate through the string in reverse order
  • If the current character is bigger than or equal to ‘mx’, assign ‘mx’ to that character and continue.
  • Let ‘i’  be the current index
  • Initialize ‘k’ with ‘i’
  • Run a loop ‘j’ from ‘i’ + 1 till the end of the string
    • If ‘S[j]’ is greater than ‘S[i]’ and is less than or equal to ‘mx’ then assign ‘mx’ to the minimum of ‘mx’ and  ‘S[j]’ and assign ‘k’ to ‘j’.
  • Swap ‘S[i]’ with ‘S[k]’
  • Sort the string from ‘i’ + 1 till the end of the string
  • Break the loop
• Convert the string ‘ans’ to an integer ‘finalAns’
• If ‘finalAns’ is greater than ‘N’ return ‘finalAns’ else return -1