greater-bigger

Given a word w, rearrange the letters of w to construct another word s in such a way that s is lexicographic-ally greater than w. In case of multiple possible answers, find the lexicographic-ally smallest one.

Input Format

The first line of input contains t, the number of test cases. Each of the next t lines contains w.

Output Format

For each testcase, output a string lexicographically bigger than w in a separate line. In case of multiple possible answers, print the lexicographically smallest one, and if no answer exists, print no answer.

Constraints

1≤t≤105

1≤|w|≤100

w will contain only lower-case English letters and its length will not exceed 100.

SAMPLE INPUT
5
ab
bb
hefg
dhck
dkhc

SAMPLE OUTPUT
ba
no answer
hegf
dhkc
hcdk

Explanation

Test case 1:

There exists only one string greater than 'ab' which can be built by   rearranging  'ab'. That is 'ba'.

**Test case 2:**

Not possible to rearrange 'bb' and get a lexicographically greater string.

**Test case 3:**

'hegf' is the next string lexicographically greater than 'hefg'.

**Test case 4:**

'dhkc' is the next string lexicographically greater than 'dhck'.

**Test case 5:**

'hcdk' is the next string lexicographically greater than 'dkhc'.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from itertools import permutations
def get(s):
	A = list(s)
	A = list(map(ord, A))
	n = len(A)

	a = -1
	for i in range(n-1, 0, -1):
		if A[i-1]<A[i]:
			a = i-1
			break
	else:
		return "no answer"

	b = -1
	for i in range(n-1, a, -1):
		if A[i]>A[a]:
			b = i
			break
	else:
		return "no answer"
	A[a], A[b] = A[b], A[a]  
	A = A[:a+1]+A[n-1:a:-1] 
	return "".join(map(chr, A))
for _ in range(eval(input())):
	s=input()
	print(get(s))
	"""p = [''.join(p) for p in permutations(s)]
	p.remove(s)
	print min(p)"""



def lexicographically_next_permutation(a):
    
	i = len(a) - 2
	while not (i < 0 or a[i] < a[i+1]):
		i -= 1
	if i < 0:
		return False
	# else
	j = len(a) - 1
	while not (a[j] > a[i]):
		j -= 1
	a[i], a[j] = a[j], a[i]        # swap
	a[i+1:] = reversed(a[i+1:])    # reverse elements from position i+1 till the end of the sequence
	return True
 
t=int(input())
for i in range(t):
	a=list(input())
	if lexicographically_next_permutation(a):
		
		sd=''
		for i in range(len(a)):
			sd=sd+a[i]
			
		print(sd);
			
		
	else:
		print("no answer");


def NextPerm(s):
	Len = len(s)
	# char at the end of string
 
	EndChar = s[Len-1]
	 
 
	for i in range (Len-2,-1,-1):
 
		# compare with char to left of the last char
 
		c = s[i]
 
		# if smaller, then it has to be substituted
 
		if(c < EndChar):
 
		# left to the char under check is remaining the same and put into buffer
 
			buff = s[:i]
			#print buff
 
			# find next biggest digit on the right starting from end and notice the last char is the smallest)
 
			for j in range(Len-1,i,-1):
 
				# check if the digit is bigger
 
				if(s[j] > c):
 
					break
 
			# Add the char to buffer
 
			buff = buff + s[j]
			 
 
			# book keep the index
			index = j
 
				 
 
			# add remaining chars in ascending order(reverse order) and put also insert C in its index
 
				  
 
			for j in range(Len-1,i,-1):
 
				# check if the the char was used to replace 'c' 
 
				if(j == index):
 
					# if yes, keep 'c' in its place
 
					buff = buff + c
 
				else:
 
					# else copy next char
 
					buff = buff + s[j]
 
						 
 
			return(buff)
 
			 
 
		# last char is stored for the loop process
 
		EndChar = c
 
		 
 
		# if char are in descending order its the biggest permutation
 
	return("no answer")
 
for _ in range(eval(input())):
	s=input()
		
 	ans=NextPerm(s)
 	print(ans)


for _ in range(eval(input())):
	s = input()
	if 1 < 0:
		print('no answer')
	else:
		w = list(s)
		ln = len(w)
		x = ln-1
		while x > 0:
			if(w[x] > w[x-1]):
				break
			x -= 1
		 
		if x == 0:
			print('no answer')
			continue
			
		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
		 
		temp = w[x]
		w[x] = mn
		w[mnx] = temp
		 
		subs = w[x+1:]
		subs.sort()
		w = w[:x+1] + subs
		st = ''.join(w)
		print(st)


t=eval(input())
while t:
	t-=1
	s=input()
	i=0
	x=-1
	while i<len(s)-1:
		if ord(s[i])<ord(s[i+1]):
			x=i
		i+=1
	if x==-1:
		print("no answer")
	else:
		y=ord(s[x])
		i=x+1
		#print x
		z=x
		diff=26
		while i<len(s):
			if ord(s[i])-y>0 and ord(s[i])-y<26:
				z=i
			i+=1
		q=list(s)
		temp=q[x]
		q[x]=q[z]
		q[z]=temp
		temp=q[x+1:]
		temp.sort()
		q=q[:x+1]+temp
		if s==''.join(q):
			print("no answer")
		else:
			print(''.join(q))        


for _ in range(eval(input())):
	x=input()
	x=list(x)
	ans=len(x)-1
	no=1
	while(ans>0):
		if(x[ans]>x[ans-1]):
			no=0
			break
		ans = ans-1
	if(no):
		print("no answer")
	else:
		check = x[ans]
		t=ans
		for i in range(ans+1,len(x)):
			if(x[i]<check and x[i]>x[ans-1]):
				check = x[i]
				t=i
		x[ans-1],x[t]= x[t],x[ans-1]
		new = x[ans:]
		new.sort()
		x = x[:ans]+new
		to_print = ""
		for i in x:
			to_print+=i
		print(to_print)

		
			 


def solve(x):
	X = list(x)
	X = list(map(ord, X))
	n = len(X)
	a = -1
	for i in range(n-1, 0, -1):
		if X[i-1] < X[i]:
			a = i-1
			break
	else:
		return "no answer"

	b = -1
	for i in range(n-1, a, -1):
		if X[i] > X[a]:
			b = i
			break
	else:
		return "no answer"
	X[a], X[b] = X[b], X[a]  
	X = X[:a+1] + X[n-1:a:-1]  
	return "".join(map(chr, X))
	
for t in range(int(input())):
	s = input()
	print(solve(s))