The following piece of code accepts as input a single string of characters and produces on standard output a string which would be the next string to appear in lexicographical order.
Definition of Lexicographical order : wiki (Also known as The Dictionary order since lexicographical order is one in which the strings would appear in a dictionary)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
# accept the raw input string orig = raw_input() # convert the string to list of its characters w = list(orig) # get length of above list ln = len(w) x = ln-1 # loop over to find the rightmost character # which is smaller than the character next to it # call it 'ref character' while x > 0: if(w[x] > w[x-1]): break x -= 1 # check if any such character is found # if no then it is not possible to make a # lexicographically bigger string with given # characters if x == 0: print 'no answer' continue # now find the smallest character to the right # of 'ref character' which is bigger than 'ref character' mn = w[x] mnx = x ix = x + 1 x -= 1 while ix < ln: if w[ix] < mn and w[ix] > w[x]: mn = w[ix] mnx = ix ix += 1 # interchange the 'ref character' and the character # thus determined temp = w[x] w[x] = mn w[mnx] = temp # take the sub string after original position of # 'ref character' and sort it. subs = w[x+1:] subs.sort() w = w[:x+1] + subs # replace this sorted string to unsorted version st = ''.join(w) # print the result. print st |