/*
* @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