We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Oops! I missed some indentation when copying. Now corrected. See my comments below:
To find the smallest one among the lexicographically greater we have to rearrange the rightmost letters.
for_inrange(int(input())):w=input().strip()n=len(w)+1forkinrange(-2,-n,-1):# So I read the word w from right to left,ifw[k]<w[k+1]:# searching for the first letter w[k] smaller than the previous (from right).print(w[:k],end='')# Then I leave the left part of the word unchanged, and print it.v=w[:k:-1]# The right part is to be rearranged - inversed first of all - to give the smallest possible.forjinrange(-k-1):# Then I look for the right place there to insert w[k] which has been found earlier.ifw[k]<v[j]:# Right place means the leftmost letter v[j] of the inversed right part v, which is greater than w[k].print(v[j]+v[:j]+w[k]+v[j+1:])# Inversion of w[k] and v[j] completes the rearrangement of the right part,break# so I print it and leave.else:# If only one (the rightmost) letter of the inversed right part v is greater than w[k], its inversion with w[k]print(v+w[k])# means just placing w[k] after the v.breakelse:# If no letter of the initial word w is smaller than the previous from right, i.e. the letters are decreasing in the word, print('no answer')# than no rearrangement gives a lexicographically greater.
Bigger is Greater
You are viewing a single comment's thread. Return to all comments →
Oops! I missed some indentation when copying. Now corrected. See my comments below:
To find the smallest one among the lexicographically greater we have to rearrange the rightmost letters.