Given a very large number (any number of digits), find the next greater number formed by permutation of digits of this number.

/*
     * The Naive approach will be to generate all permutations of the string and check the next greater number.
     * Another Approach:
     * Start traversing from second Last digit of the number.
     * Check on right of current digit (starting from rightmost digit) if there is any digit greater than current digit.
     * If there is any then return its position.
     * else return -1.
     * swap currentPosition digit with returnedPosition digit.
     * Now Reverse the String after currentPosition till end.
     * As from currentPosition till end digits will be in descending order but to find next greatest digits should be in ascending order.
     * Reversing ascending order means descending order hence, reversing string after currentPosition digit.
     * If leftmost digit is reached and no such digit is found then display NO SUCH NUMBER EXIST.
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Solution {

     private String number ;
 
     public void initialize()
     {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          try
          {
               number = br.readLine();
          } catch (IOException e)
          {
               e.printStackTrace();
          }
          System.out.println("Next Greater Number is : " + getNextGreaterNumber());
     }
 
     public int getGreaterinRightHalf(int digit , int pos)
     {
          for(int i = number.length()-1 ; i > pos ; i--)
          {
               if(digit < Integer.parseInt(Character.toString(number.charAt(i))))
               {
                    return i;
               }
          }
          return -1;
     }
 
     public String getReverseString(String str)
     {
          String reverseStr = "";
          for(int i = str.length()-1 ; i>=0 ; i--)
          {
               reverseStr += str.charAt(i) +"";
          }
          return reverseStr;
     }
   
   
     public String getNextGreaterNumber()
     {
          int swapPos = -1;
          int i = number.length()-2 ;
          for( ; i > 0 ; i--)
          {
               swapPos = getGreaterinRightHalf(Integer.parseInt(Character.toString(number.charAt(i))),i );
               if(swapPos != -1)
               {
                    break;
               }
          }
          String finalString;
          if(swapPos == -1)
          {
               finalString = "NO SUCH NUMBER EXIST";
          }
          else
          {
           
               finalString = number.substring(0, i) + number.charAt(swapPos) + getReverseString(number.substring(i+1, swapPos) + number.charAt(i) + number.substring(swapPos+1));
          }
          return finalString;
     }

 
     public static void main(String args[])
     {
          Solution s = new Solution();
          s.initialize();
       
     }
}