Given a non-negative number N in the form of string. The task is to apply at most one swap operation on the number N so that the result is just a previous possible number.
Note:  Leading zeros are not allowed.
 
Example 1:
Input :
S = "12435"
Output: 
12345
Explanation:
Although the number 12354 
will be the largest smaller 
number from 12435. But it is 
not possible to make it using 
only one swap. So swap 
4 and 3 and get 12345.
 
Example 2:
Input: 
S = " 12345"
Output: 
-1
Explanation:
Digits are in increasing order. 
So it is not possible to 
make a smaller number from it.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function previousNumber() which takes the string S and returns the previous number of S. If no such number exists return -1;
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
2<=|Number length |<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Starter code: #User function Template for python3
class Solution:
    def previousNumber (ob,S):
        # code here 
        

Solutions:
class Solution:

	def previousNumber(ob, S):
		i = len(S) - 1
		f = 0
		while i > 0:
			if S[i] < S[i - 1]:
				f = 1
				j = i
				x = S[i - 1]
				first = i - 1
				while j < len(S):
					if x != S[j] and S[j] < S[i - 1]:
						last = j
						x = S[j]
					elif S[j] > S[i - 1]:
						break
					j += 1
				if f == 1:
					break
			i -= 1
		if f == 0:
			return -1
		ans = ''
		for i in range(len(S)):
			if i == first:
				ans += S[last]
			elif i == last:
				ans += S[first]
			else:
				ans += S[i]
		if ans[0] == '0':
			return -1
		return ans


class Solution:

	def previousNumber(ob, s):
		n = len(s)
		arr = list(s)
		flag = False
		for i in range(n - 1):
			if arr[i] <= arr[i + 1]:
				continue
			else:
				Flag = True
				break
		if flag:
			return -1
		idx = None
		for i in range(n - 1, 0, -1):
			if arr[i - 1] > arr[i]:
				idx = i - 1
				break
		if idx == None:
			return -1
		temp = '-999999'
		for j in range(n - 1, idx, -1):
			if arr[j] < arr[idx]:
				if arr[j] >= temp:
					idx2 = j
					temp = arr[idx2]
		(arr[idx], arr[idx2]) = (arr[idx2], arr[idx])
		ans = ''.join(arr)
		if ans[0] == '0':
			return -1
		return ans


class Solution:

	def previousNumber(ob, S):
		i = len(S) - 2
		while i >= 0 and S[i] <= S[i + 1]:
			i -= 1
		if i < 0:
			return '-1'
		j = len(S) - 1
		while j > i and S[i] <= S[j]:
			j -= 1
		while j > 0 and S[j - 1] == S[j]:
			j -= 1
		S = list(S)
		(S[i], S[j]) = (S[j], S[i])
		if S[0] == '0':
			return '-1'
		return ''.join(S)


class Solution:

	def previousNumber(ob, s):

		def lowerind(j, a):
			maxi = -1
			k = 0
			for i in range(j, len(a)):
				if a[i] < a[j - 1]:
					if a[i] > maxi:
						maxi = a[i]
						k = i
			return k
		l = [int(x) for x in s]
		for i in range(len(s) - 1, 0, -1):
			if l[i - 1] > l[i]:
				ans = lowerind(i, l)
				(l[ans], l[i - 1]) = (l[i - 1], l[ans])
				break
		r = ''.join([str(g) for g in l])
		if s == r or r[0] == '0':
			return -1
		else:
			return r


class Solution:

	def previousNumber(ob, s):
		s = list(s)
		ref = 0
		for i in range(len(s) - 2, -1, -1):
			x = s[i + 1]
			if s[i] > x:
				y = i
				ref = 1
				break
		if ref == 0:
			return -1
		d = int(s[y]) - int(s[y + 1])
		j = y + 1
		for k in range(j, len(s), 1):
			diff = int(s[y]) - int(s[k])
			if diff > 0 and diff < d and (s[y] != s[k]):
				d = diff
				j = k
		(s[y], s[j]) = (s[j], s[y])
		if s[0] == '0':
			return -1
		return ''.join(s)


class Solution:

	def prev(self, s):
		n = len(s)
		f = 0
		for i in range(n - 1, 0, -1):
			if s[i - 1] > s[i]:
				p = i - 1
				f = 1
				break
		if f == 0:
			return '-1'
		for i in range(n - 1, p, -1):
			if s[i] < s[p]:
				m = i
				while s[m] == s[m - 1]:
					m -= 1
				break
		l = []
		for i in s:
			l.append(i)
		(l[m], l[p]) = (l[p], l[m])
		return ''.join(l)

	def previousNumber(self, S):
		d = self.prev(S)
		if d[0] == '0':
			return '-1'
		return d


class Solution:

	def previousNumber(ob, S):
		index = -1
		S = list(S)
		n = len(S)
		for i in range(n - 2, -1, -1):
			if int(S[i]) > int(S[i + 1]):
				index = i
				break
		smallGreatDgt = -1
		for i in range(n - 1, index, -1):
			if smallGreatDgt == -1 and int(S[i]) < int(S[index]):
				smallGreatDgt = i
			elif index > -1 and int(S[i]) >= int(S[smallGreatDgt]) and (int(S[i]) < int(S[index])):
				smallGreatDgt = i
		if index == -1:
			return ''.join('-1')
		else:
			(S[index], S[smallGreatDgt]) = (S[smallGreatDgt], S[index])
		if S[0] == '0':
			return '-1'
		return ''.join(S)


class Solution:

	def previousNumber(ob, S):
		l = []
		a = ''
		ind = -1
		inc = -1
		for i in S:
			l.append(i)
		for i in range(len(l) - 1, 0, -1):
			if int(l[i]) < int(l[i - 1]):
				ind = i - 1
				break
		if ind == -1:
			return '-1'
		for j in range(ind + 1, len(l)):
			if int(l[j]) < int(l[ind]):
				if inc == -1:
					inc = j
				elif int(l[j]) > int(l[inc]):
					inc = j
		x = l[inc]
		l[inc] = l[ind]
		l[ind] = x
		for i in l:
			a = a + i
		if a.startswith('0') or S == a:
			return -1
		return a
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.previousNumber(S))


class Solution:

	def previousNumber(ob, S):
		S = list(S)
		idx1 = -1
		for i in range(len(S) - 1, 0, -1):
			if S[i] < S[i - 1]:
				idx1 = i - 1
				break
		if idx1 == -1:
			return -1
		mx = S[idx1 + 1]
		idx2 = idx1 + 1
		for i in range(idx1 + 1, len(S)):
			if S[i] > mx and S[i] < S[idx1]:
				mx = S[i]
				idx2 = i
		(S[idx2], S[idx1]) = (S[idx1], S[idx2])
		if S[0] == '0':
			return -1
		return ''.join(S)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.previousNumber(S))


class Solution:

	def previousNumber(ob, s):
		n = len(s)
		arr = list(s)
		flag = False
		for i in range(n - 1):
			if arr[i] <= arr[i + 1]:
				continue
			else:
				Flag = True
				break
		if flag:
			return -1
		idx = None
		for i in range(n - 1, 0, -1):
			if arr[i - 1] > arr[i]:
				idx = i - 1
				break
		if idx == None:
			return -1
		temp = '-999999'
		for j in range(n - 1, idx, -1):
			if arr[j] < arr[idx]:
				if arr[j] >= temp:
					idx2 = j
					temp = arr[idx2]
		(arr[idx], arr[idx2]) = (arr[idx2], arr[idx])
		ans = ''.join(arr)
		if ans[0] == '0':
			return -1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.previousNumber(S))


class Solution:

	def lower_bound(ob, A, i):
		m = -1
		k = 0
		for j in range(i, len(A)):
			if A[i - 1] > A[j]:
				if m < int(A[j]):
					m = int(A[j])
					k = j
		return k

	def previousNumber(ob, S):
		A = list(S)
		t = 0
		d = 0
		for i in range(len(S) - 1, 0, -1):
			if A[i] < A[i - 1]:
				t = ob.lower_bound(A, i)
				(A[t], A[i - 1]) = (A[i - 1], A[t])
				break
		r = ''.join(A)
		if S == r or r[0] == '0':
			return -1
		else:
			return r


class Solution:

	def previousNumber(ob, S):
		stack = []
		n = len(S)
		i = n - 1
		while i >= 0:
			digit = int(S[i])
			if not stack or int(S[stack[-1]]) >= digit:
				stack.append(i)
			else:
				element = -1
				swap_idx = -1
				while stack:
					curr_i = stack.pop()
					e = int(S[curr_i])
					if digit > e and e > element:
						element = e
						swap_idx = curr_i
				if S[swap_idx] == '0' and i == 0:
					return -1
				return S[:i] + S[swap_idx] + S[i + 1:swap_idx] + S[i] + S[swap_idx + 1:]
			i -= 1
		return -1


class Solution:

	def previousNumber(ob, s):
		n = len(s)
		p = -1
		q = 0
		for i in range(n - 1, 0, -1):
			if s[i - 1] > s[i]:
				p = i - 1
				q = i
				for j in range(p, n):
					if s[j] > s[q] and s[j] < s[p]:
						q = j
				break
		if p < 0:
			return '-1'
		if p == 0 and s[p + 1] == '0':
			return '-1'
		s = list(s)
		(s[p], s[q]) = (s[q], s[p])
		return ''.join(s)


class Solution:

	def previousNumber(ob, s):
		s = list(s)
		n = len(s)
		i = n - 1
		c = 0
		ind = -1
		for i in range(n - 1, 0, -1):
			if s[i] < s[i - 1]:
				ind = i - 1
				break
		if ind == -1:
			return ind
		j = i
		for i in range(ind + 2, n):
			if s[i] < s[ind] and s[i] > s[j]:
				j = i
		if s[j] == '0' and ind == 0:
			return -1
		(s[ind], s[j]) = (s[j], s[ind])
		return ''.join(s)


class Solution:

	def previousNumber(ob, S):
		lis = list(S)
		i = len(lis) - 2
		while i >= 0:
			if int(lis[i]) > int(lis[i + 1]):
				break
			i = i - 1
		else:
			return -1
		j = i + 2
		k = i + 1
		max_ele = int(lis[k])
		while j < len(lis):
			if max_ele < int(lis[j]) and int(lis[j]) < int(lis[i]):
				max_ele = int(lis[j])
				k = j
			j = j + 1
		if max_ele == 0 and i == 0:
			return -1
		temp = lis[i]
		lis[i] = lis[k]
		lis[k] = temp
		return ''.join(lis)


class Solution:

	def previousNumber(ob, s):
		s = list(s)
		largest = len(s) - 2
		while largest >= 0 and s[largest] <= s[largest + 1]:
			largest -= 1
		if largest < 0:
			return -1
		smallest = len(s) - 1
		while smallest > largest and s[largest] <= s[smallest]:
			smallest -= 1
		while smallest > 0 and s[smallest - 1] == s[smallest]:
			smallest -= 1
		(s[smallest], s[largest]) = (s[largest], s[smallest])
		if s[0] == '0':
			return -1
		return ''.join(s)


class Solution:

	def previousNumber(ob, S):
		n = len(S)
		index = -1
		for i in range(n - 2, -1, -1):
			if S[i] > S[i + 1]:
				index = i
				break
		if index == -1:
			return -1
		ma = S[index + 1]
		i2 = index + 1
		for i in range(index + 1, n, 1):
			if S[i] < S[index] and S[i] > ma:
				i2 = i
				ma = S[i]
		if index == 0 and S[i2] == '0':
			return -1
		else:
			li = list(S)
			temp = li[i2]
			li[i2] = li[index]
			li[index] = temp
			return ''.join(li)


class Solution:

	def previousNumber(ob, s):
		res = ''
		l = []
		for i in s:
			l.append(int(i))
		n = len(l)
		i = n - 1
		maxi = -1
		while i - 1 >= 0 and l[i] >= l[i - 1]:
			i -= 1
		if i <= 0:
			return -1
		ind1 = i - 1
		ind2 = -1
		for i in range(ind1 + 1, n):
			if l[i] < l[ind1]:
				if ind2 == -1:
					ind2 = i
				elif l[i] > l[ind2]:
					ind2 = i
		(l[ind1], l[ind2]) = (l[ind2], l[ind1])
		for i in l:
			res += str(i)
		if res[0] != '0':
			return res
		return -1


class Solution:

	def previousNumber(ob, s):
		n = len(s)
		for i in range(n - 1, 0, -1):
			if s[i] < s[i - 1]:
				if i == 1:
					if s[i] == '0':
						break
				j = i
				for k in range(i + 1, n):
					if s[k] < s[i - 1]:
						if s[j] != s[k]:
							j = k
					else:
						break
				return s[:i - 1] + s[j] + s[i:j] + s[i - 1] + s[j + 1:]
		return -1


class Solution:

	def previousNumber(ob, s):
		n = len(s)
		for i in range(n - 1, 0, -1):
			if s[i] < s[i - 1] and (s[i] != '0' or i - 1 != 0):
				fi = i - 1
				li = i
				for i in range(li, n):
					if s[fi] > s[i] > s[li]:
						li = max(li, i)
				ns = ''
				for j in range(n):
					if j == li:
						ns += s[fi]
					elif j == fi:
						ns += s[li]
					else:
						ns += s[j]
				return ns
		return -1


class Solution:

	def previousNumber(ob, S):
		for i in range(len(S) - 2, -1, -1):
			if int(S[i]) > int(S[i + 1]):
				maxElIndex = i + 1
				for j in range(i + 1, len(S)):
					if S[j] > S[maxElIndex] and S[j] < S[i]:
						maxElIndex = j
				s = list(S)
				(s[i], s[maxElIndex]) = (s[maxElIndex], s[i])
				s = ''.join(s)
				if s.lstrip('0') == s:
					return ''.join(s)
		return -1


class Solution:

	def previousNumber(self, s):
		idxs = [-1 for _ in range(10)]
		for i in range(len(s) - 1, -1, -1):
			n = ord(s[i]) - ord('0')
			for j in range(n - 1, -1, -1):
				if idxs[j] >= 0 and (not (i == 0 and j == 0)):
					return s[:i] + chr(j + ord('0')) + s[i + 1:idxs[j]] + s[i] + s[idxs[j] + 1:]
			idxs[n] = i
		return -1


class Solution:

	def previousNumber(ob, S):
		s = list(S[::-1])
		count = 0
		for i in range(len(s) - 1):
			if s[i] < s[i + 1]:
				c = i + 1
				count += 1
				break
		if count != 0:
			if len(S) >= 2:
				for j in range(c):
					p = s[j]
					if s[j] == s[j + 1]:
						continue
					if s[j] < s[c]:
						s[j] = s[c]
						s[c] = p
						break
		b = ''
		for i in s:
			b += i
		a = b[::-1]
		if a == S:
			return -1
		if a[0] == '0':
			return -1
		return a


class Solution:

	def previousNumber(ob, S):
		l = list(S)
		for i in range(len(l) - 1, -1, -1):
			if i > 0 and l[i - 1] > l[i]:
				break
		if i == 0:
			return -1
		minn = -1
		minn_ind = -1
		for j in range(i, len(l)):
			if minn != l[j] and l[j] < l[i - 1]:
				minn_ind = j
				minn = l[j]
		(l[i - 1], l[minn_ind]) = (l[minn_ind], l[i - 1])
		if l[0] == '0':
			return -1
		return ''.join(l)


class Solution:

	def previousNumber(ob, S):
		s = str(int(S))
		j = len(s) - 2
		while j >= 0:
			if j == 0 and int(s[j + 1]) == 0:
				j -= 1
				continue
			if int(s[j]) > int(s[j + 1]):
				v = j
				c = j + 1
				break
			j -= 1
		else:
			return -1
		for i in range(c + 1, len(s)):
			if int(s[v]) > int(s[i]) and int(s[c]) < int(s[i]):
				c = i
		return s[:v] + s[c] + s[v + 1:c] + s[v] + s[c + 1:]


class Solution:

	def previousNumber(ob, S):
		s = list(map(int, list(S)))
		flag = False
		index = 0
		for i in range(len(s) - 1, 0, -1):
			if i == 1 and s[i] == 0:
				break
			if s[i] < s[i - 1]:
				flag = True
				index = i - 1
				break
		if not flag:
			return -1
		swap = 0
		maxx = -1
		for i in range(index, len(s)):
			if s[index] > s[i] and s[i] > maxx:
				maxx = s[i]
				swap = i
		(s[index], s[swap]) = (s[swap], s[index])
		s = list(map(str, s))
		return ''.join(s)


class Solution:

	def previousNumber(ob, S):
		if len(S) == 1:
			return -1
		S = list(S)
		for i in range(len(S) - 2, -1, -1):
			if S[i] <= S[i + 1]:
				continue
			else:
				break
		ind = i
		if S[ind] <= S[ind + 1]:
			return -1
		swapInd = -1
		val = '-1'
		for i in range(i + 1, len(S)):
			if S[ind] > S[i]:
				if S[i] > val:
					swapInd = i
					val = S[i]
		(S[ind], S[swapInd]) = (S[swapInd], S[ind])
		if S[0] == '0':
			return -1
		return ''.join(S)


class Solution:

	def previousNumber(ob, S):
		ans = []
		n = len(S) - 1
		i = n
		fst = -1
		while i > 0:
			if S[i] < S[i - 1]:
				fst = i - 1
				break
			i -= 1
		if fst == -1:
			return -1
		i = fst + 1
		scd = fst + 1
		cond = True
		while i <= n:
			if S[i] < S[fst]:
				cond = False
				if S[i] > S[scd]:
					scd = i
			i += 1
		if cond:
			return -1
		ans = S[:fst] + S[scd] + S[fst + 1:scd] + S[fst] + S[scd + 1:]
		if ans[0] == '0':
			return -1
		return ans


class Solution:

	def previousNumber(ob, S):
		ind = -1
		n = len(S)
		for i in range(n - 1, 0, -1):
			if S[i - 1] > S[i]:
				ind = i - 1
				break
		if ind == -1:
			return -1
		tmp = -1
		for i in range(n - 1, ind, -1):
			if tmp == -1 and S[i] < S[ind]:
				tmp = i
			elif S[tmp] <= S[i] and S[i] < S[ind]:
				tmp = i
		l = list(S)
		(l[ind], l[tmp]) = (l[tmp], l[ind])
		if l[0] == '0':
			return -1
		return ''.join(l)
		return ''.join(l)


from collections import defaultdict
from math import *

class Solution:

	def previousNumber(ob, S):
		s = set()
		S = list(S)
		d = defaultdict(list)
		for i in range(len(S) - 1, -1, -1):
			max1 = -inf
			for j in s:
				if S[i] > j:
					max1 = max(max1, int(j))
			if max1 != -inf:
				(S[i], S[d[str(max1)]]) = (S[d[str(max1)]], S[i])
				break
			else:
				d[S[i]] = i
				s.add(S[i])
		else:
			return -1
		if S[0] == '0':
			return -1
		return ''.join(S)


class Solution:

	def previousNumber(ob, S):
		s = list(S)
		n = len(S)
		for i in range(0, len(S) - 1):
			if int(s[n - 1 - i]) < int(s[n - 2 - i]):
				m = n - 1 - i
				val = int(s[n - 2 - i])
				pos = n - 1 - i
				while pos < len(s):
					if int(s[pos]) < val:
						if int(s[pos]) > int(s[m]):
							m = pos
					pos += 1
				(s[m], s[n - 2 - i]) = (s[n - 2 - i], s[m])
				if s[0] == '0':
					return -1
				else:
					return ''.join(s)
		return -1


class Solution:

	def previousNumber(ob, S):
		arr = list(S)
		index1 = index2 = -1
		for i in range(len(arr) - 1, 0, -1):
			if arr[i - 1] > arr[i]:
				index1 = i - 1
				break
			index1 -= 1
		if index1 < 0:
			return '-1'
		i = len(arr) - 1
		while i > index1:
			if arr[i] < arr[index1]:
				while arr[i] == arr[i - 1]:
					i -= 1
				index2 = i
				break
			i -= 1
		(arr[index1], arr[index2]) = (arr[index2], arr[index1])
		if arr[0] == '0':
			return '-1'
		return ''.join(arr)


class Solution:

	def previousNumber(ob, S):
		s = ''
		i1 = -1
		for i in range(len(S) - 1):
			if int(S[i]) > int(S[i + 1]):
				i1 = i
		if i1 == -1:
			return -1
		else:
			i2 = -1
			for i in range(i1 + 1, len(S)):
				if S[i] < S[i1]:
					if i2 == -1:
						i2 = i
					elif S[i] > S[i2]:
						i2 = i
		for i in range(len(S)):
			if i == i1:
				s = s + S[i2]
			elif i == i2:
				s = s + S[i1]
			else:
				s = s + S[i]
		if s[0] == '0':
			return -1
		return s


class Solution:

	def previousNumber(ob, s):
		s = list(s)
		l = len(s) - 2
		while l >= 0 and s[l] <= s[l + 1]:
			l -= 1
		if l == -1:
			return -1
		r = len(s) - 1
		while r > l and s[l] <= s[r]:
			r -= 1
		while r > l and s[r] == s[r - 1]:
			r -= 1
		(s[l], s[r]) = (s[r], s[l])
		if s[0] == '0':
			return -1
		else:
			return ''.join(s)


class Solution:

	def previousNumber(ob, S):
		n = len(S)
		pos = -1
		for i in range(0, n - 1):
			if S[i + 1] < S[i]:
				pos = i
		if pos == -1:
			return -1
		for i in range(pos + 1, n):
			if S[i] < S[pos] and S[i] != S[i - 1]:
				pos1 = i
		arr = list(S)
		(arr[pos], arr[pos1]) = (arr[pos1], arr[pos])
		ans = ''.join(arr)
		if ans[0] == '0':
			return -1
		return ans


class Solution:

	def previousNumber(self, S):
		mn = S[-1]
		for i in range(len(S) - 2, -1, -1):
			if S[i] > mn:
				break
			mn = min(mn, S[i])
		else:
			return -1
		index = i
		mn = ''
		for j in range(i, len(S)):
			if S[j] < S[i] and S[j] > mn:
				mn = S[j]
				index = j
		ans = S[:i] + mn + S[i + 1:index] + S[i] + S[index + 1:]
		if ans[0] == '0':
			return -1
		return ans


import math

class Solution:

	def previousNumber(ob, S):
		res = -1
		S.strip(' ')
		idx = -1
		maxi = -math.inf
		maxIdx = -1
		for i in range(len(S) - 1, 0, -1):
			if int(S[i]) >= int(S[i - 1]):
				continue
			else:
				idx = i - 1
				break
		if idx != -1:
			for i in range(idx + 1, len(S)):
				if int(S[i]) < int(S[idx]) and int(S[i]) > maxi:
					maxi = int(S[i])
					maxIdx = i
			t = list(S)
			(t[idx], t[maxIdx]) = (t[maxIdx], t[idx])
			res = ''.join(t)
		else:
			return -1
		if res[0] == '0':
			return -1
		return res


class Solution:

	def previousNumber(ob, S):
		arr = [int(i) for i in S]
		n = len(arr)
		j = -1
		m = 0
		for i in range(1, n):
			if arr[i] < arr[i - 1]:
				j = i - 1
		if j == -1:
			return str(-1)
		k = 0
		m = -1
		for i in range(j + 1, n):
			if arr[i] > m and arr[i] < arr[j]:
				m = arr[i]
				k = i
		(arr[j], arr[k]) = (arr[k], arr[j])
		ans = ''
		for i in arr:
			ans += str(i)
		if ans[0] == '0':
			return str(-1)
		return ans


class Solution:

	def previousNumber(ob, S):
		l = list(S)
		i = len(S) - 2
		j = len(S) - 1
		while i >= 0 and S[i + 1] >= S[i]:
			i -= 1
		if i == -1:
			return -1
		minn = -1
		ind = -1
		while j >= i:
			if S[j] < S[i]:
				if int(S[j]) >= minn:
					minn = int(S[j])
					ind = j
			j -= 1
		(l[i], l[ind]) = (l[ind], l[i])
		if l[0] == '0':
			return -1
		if int(''.join(l)) == S:
			return -1
		return int(''.join(l))


class Solution:

	def previousNumber(ob, S):
		arr = list(S)
		n = len(arr)
		flag = False
		ind = None
		for i in range(n - 1, 0, -1):
			if arr[i - 1] > arr[i]:
				ind = i - 1
				break
		if ind == None:
			return -1
		ans = str(-float('inf'))
		ss = -1
		for j in range(n - 1, ind, -1):
			if arr[j] < arr[ind]:
				if arr[j] >= ans:
					ss = j
					ans = arr[ss]
		(arr[ind], arr[ss]) = (arr[ss], arr[ind])
		ans = ''.join(arr)
		if ans[0] == '0':
			return -1
		return ans


class Solution:

	def previousNumber(ob, s):
		n = len(s)
		s = list(s)
		s1 = -1
		for i in range(n - 1):
			if s[i] > s[i + 1]:
				s1 = i
		if s1 == -1:
			return '-1'
		for i in range(s1 + 1, n):
			if s[i] < s[s1] and s[i] != s[i - 1]:
				s2 = i
		(s[s1], s[s2]) = (s[s2], s[s1])
		res = ''.join(s)
		if res[0] == '0':
			return '-1'
		return res


class Solution:

	def previousNumber(self, s):
		(n, a) = (len(s), list(s))
		position = -1
		memo = {a[-1]: n - 1}
		for i in range(n - 2, -1, -1):
			if a[i + 1] < a[i]:
				position = i
				break
			memo[a[i]] = i
		if position == -1:
			return -1
		lt = sorted(memo.items())[::-1]
		post2 = -1
		for i in lt:
			if i[0] < a[position]:
				post2 = i[1]
				break
		(a[position], a[post2]) = (a[post2], a[position])
		if a[0] == '0':
			return -1
		return ''.join(a)


class Solution:

	def previousNumber(self, s):
		n = len(s)
		(id1, id2) = (-1, -1)
		i = n - 2
		while i >= 0:
			if s[i] > s[i + 1]:
				id1 = i
				break
			i -= 1
		if i == -1:
			return '-1'
		i = n - 1
		while i > id1:
			if s[i] < s[id1]:
				while s[i] == s[i - 1]:
					i -= 1
				id2 = i
				break
			i -= 1
		if id2 == -1:
			return '-1'
		s = list(s)
		(s[id1], s[id2]) = (s[id2], s[id1])
		if s[0] == '0':
			return '-1'
		return ''.join(s)


class Solution:

	def previousNumber(ob, S):
		l = list(S)
		for i in range(len(l)):
			l[i] = int(l[i])
		f = 0
		for i in range(len(l) - 2, -1, -1):
			if l[i] > l[i + 1]:
				f = 1
				break
		if f == 0:
			return -1
		for j in range(len(l) - 1, i, -1):
			if l[i] > l[j]:
				break
		m = l[j]
		while j >= 0 and l[j] == m:
			j = j - 1
		if j < 0 or l[j] != m:
			j = j + 1
		if l[j] == 0 and i == 0:
			return -1
		(l[i], l[j]) = (l[j], l[i])
		ans = 0
		for i in range(len(l)):
			ans = ans * 10 + l[i]
		return ans


class Solution:

	def previousNumber(ob, S):
		i = 0
		p1 = -1
		p2 = -1
		i = len(S) - 1
		while i > 0:
			if S[i] < S[i - 1]:
				if i - 1 == 0 and S[i] == '0':
					pass
				else:
					p1 = i - 1
					p2 = i
					break
			i -= 1
		if p1 == -1:
			return -1
		i = p2 + 1
		while i < len(S):
			if S[i] < S[p1] and S[i] > S[p2]:
				p2 = i
			i += 1
		S = S[0:p1] + S[p2] + S[p1 + 1:p2] + S[p1] + S[p2 + 1:]
		return S


class Solution:

	def previousNumber(ob, S):
		lst1 = list(S)
		lst2 = list(S)
		lst2.sort()
		if lst2 == lst1:
			return -1

		def find(k, n):
			temp = -1
			out = 0
			for i in range(len(k)):
				if int(k[i]) > temp and int(k[i]) < int(n):
					out = i
					temp = int(k[i])
			return out
		for i in range(len(S) - 1, 0, -1):
			if int(S[i]) < int(S[i - 1]):
				break
		k = list(S[i - 1:])
		if len(k) == 2:
			p = S[:len(S) - 2] + k[1] + k[0]
			return p
		index = find(k[1:], k[0])
		if len(k) == len(S) and k[index + 1] == '0':
			return -1
		(k[0], k[index + 1]) = (k[index + 1], k[0])
		op = ''.join(k)
		out = S[:len(S) - len(k)] + op
		return out


class Solution:

	def previousNumber(ob, S):
		S = S.strip()
		length = len(S)
		largest = length - 2
		for i in range(length - 2, -1, -1):
			if S[largest] <= S[largest + 1]:
				largest -= 1
		if largest < 0:
			return '-1'
		smallest = length - 1
		while smallest > largest and S[largest] <= S[smallest]:
			smallest -= 1
		while smallest > 0 and S[smallest - 1] == S[smallest]:
			smallest -= 1
		S = list(S)
		(S[largest], S[smallest]) = (S[smallest], S[largest])
		S = ''.join(S)
		if S[0] == '0':
			return '-1'
		return S


class Solution:

	def previousNumber(ob, s):
		n = len(s)
		i = n - 1
		for i in range(n - 1, 0, -1):
			if i == 1 and s[i] == '0' and (int(s[i - 1]) > int(s[i])):
				continue
			if int(s[i - 1]) > int(s[i]):
				s = list(s)
				val = -1
				idx = -1
				for j in range(i, n):
					if int(s[j]) > val and int(s[j]) < int(s[i - 1]):
						val = int(s[j])
						idx = j
				(s[i - 1], s[idx]) = (s[idx], s[i - 1])
				return ''.join(s)
		return -1


class Solution:

	def solve(ob, S, idx, n):
		x = None
		for i in range(n - 1, idx, -1):
			if S[i] < S[idx] and S[i - 1] != S[i]:
				x = i
				break
		S = S[:idx] + S[x] + S[idx + 1:x] + S[idx] + S[x + 1:]
		low = x
		high = n - 1
		return S

	def previousNumber(ob, S):
		n = len(S)
		for i in range(n - 1, 0, -1):
			if S[i] < S[i - 1]:
				ans = ob.solve(S, i - 1, n)
				if ans[0] == '0':
					return -1
				return ans
		return -1


class Solution:

	def previousNumber(ob, s):
		curr = 0
		for i in range(len(s) - 2, -1, -1):
			if s[i] > s[i + 1]:
				curr = i + 1
				break
		else:
			return -1
		prev = curr - 1
		mx = curr
		for i in range(curr, len(s)):
			if s[i] > s[mx] and s[i] < s[prev]:
				mx = i
		(x, y) = (s[prev], s[mx])
		s = s[:prev] + y + s[prev + 1:mx] + x + s[mx + 1:]
		s = s[:mx + 1] + ''.join(sorted(s[mx + 1:]))
		if s[0] == '0':
			return -1
		return s


class Solution:

	def previousNumber(ob, S):
		s = list(S)
		last = -1
		choosen_index = 0
		flag = False
		if len(s) == 1:
			return -1
		for i in range(len(s) - 2, -1, -1):
			if int(s[i + 1]) < int(s[i]):
				if s[i + 1] == '0' and i == 0:
					return -1
				choosen_index = i
				flag = True
				break
		inv = s[i]
		if flag:
			gr = -1
			ind = 0
			for j in range(i, len(s)):
				if int(inv) > int(s[j]):
					if gr < int(s[j]):
						gr = int(s[j])
						ind = j
			(s[i], s[ind]) = (s[ind], s[i])
			return ''.join(s)
		return -1