Tuesday, 29 July 2014

UVa 146 - ID Codes



/*
 * @author Divyanhsu
 * @mail divyanshu17x@gmail.com
 * @place GNDU RC SATHIALA
 * @date 29 / 07 / 2014
 * @judge uva.onlinejudge.org
 * @verdict Accepted
 * @problem  UVa 146 - ID Codes
 * @problemType  next permutation
 */

 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
 class  Main {
     public static void main(String args[]) throws IOException{
         BufferedReader reader =  new BufferedReader(new InputStreamReader(System.in)) ; 
           
            //read the code
            String code = reader.readLine();
           
           
           
            //evaluate next permutation of code string  until a sentinel # is read
            while(!code.equals("#"))
            {
                //Linked list of character read from right
                LinkedList <Character> charsReadList = new LinkedList<>();
               
                //flag  to find any rightmost character
                //greater then any right most character before it
                boolean found = false ;
               
                char charArray[]  = code.toCharArray();
               
                //iterator variable
                int i = 0 ;
               
                //loop through the right most character of string
                for( i = code.length() - 1 ; !found && i >= 0 ; --i )
                {
                    char currentChar = charArray[i];
                   
                    //create an iterator for linked list of read characters
                    Iterator<Character> iter =  charsReadList.iterator();
                   
                    //loop until we  find the  rightmost read character from list
                    //to be greater then current read character
                    // or all chars of list are compared
                    while( !found && iter.hasNext() )
                    {
                        char x = iter.next();
                        if(x > currentChar )
                        {
                            //turn the flag on
                            found = true ;
                           
                            //place the compared character from list in place of current read character
                            charArray[i] = x ;
                           
                            //remove the compared character from list
                            iter.remove();
                           
                           
                        }
                    }
                   
                    //add the read  current character to list
                    charsReadList.add(currentChar);
                   
                   
                }
               
                if(found)
                {
                    //shift the iterator variable i at index just\
                    //before the index of current character read
                    //which has been replaced by right most charcter greater then it
                    i += 2 ;
                   
                    //sort the read characters list
                    Collections.sort(charsReadList);
                   
                    Iterator<Character> iter = charsReadList.iterator();
                   
                    //place the read charatcer list starting from position i
                    while(iter.hasNext())
                    {
                        charArray[i++] = iter.next();
                    }
                   
                    //print the next permuation string
                    String nextPerm = "";
                    for(int m = 0 , length = charArray.length ; m < length ; ++m)
                    {
                        nextPerm += charArray[m];
                    }
                    System.out.println(nextPerm);
                   
                }
                else
                {
                    //else print no  next permuatation successor found
                    System.out.println("No Successor");
                }
               
                //read the next case
                code = reader.readLine();
            }
           
            reader.close();
   
     }
 }



   

No comments:

Post a Comment