Given a non-negative number num in the form of string. The task is to apply at most one swap operation on the number num so that the result is the next higher number.
Example 1:
Input: num = "768"
Output: "786"
Explanation: This is next higher
number that we can get.
Example 2:
Input: num = "333"
Output: "-1"
Explanation: There is no higher
number than 333. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function nxtHighUsingAtMostOneSwap() which takes the string num as inputs and returns the answer.
Expected Time Complexity: O(|num|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |num| ≤ 10^{5}
|num| denotes the length of the string num.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Starter code: #User function Template for python3
class Solution:
    def nxtHighUsingAtMostOneSwap(self, num): 
        # code here

Solutions:
class Solution:

	def nxtHighUsingAtMostOneSwap(self, num):
		a = [c for c in num]
		n = len(num)
		marked = [-1] * 10
		marked[ord(a[n - 1]) - ord('0')] = n - 1
		for i in range(n - 2, -1, -1):
			pos = -1
			for j in range(ord(a[i]) - ord('0') + 1, 10):
				if marked[j] != -1 and (pos == -1 or pos < marked[j]):
					pos = marked[j]
			if pos != -1:
				(a[pos], a[i]) = (a[i], a[pos])
				num2 = ''.join(a)
				return num2
			marked[ord(a[i]) - ord('0')] = i
		return '-1'


class Solution:

	def nxtHighUsingAtMostOneSwap(self, num):
		s = []
		n = len(num)
		pos = -1
		for i in range(n - 1, -1, -1):
			while len(s) > 0 and num[s[-1]] > num[i]:
				if pos < 0 or num[pos] != num[s[-1]]:
					pos = s[-1]
				s.pop()
			if pos < 0:
				s.append(i)
			else:
				break
		if pos == -1:
			return '-1'
		num_list = list(num)
		(num_list[i], num_list[pos]) = (num_list[pos], num_list[i])
		return ''.join(num_list)


class Solution:

	def nxtHighUsingAtMostOneSwap(self, 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 nxtHighUsingAtMostOneSwap(self, n):
		l = list(str(n))
		x = len(l)
		i = x - 1
		while i > 0 and l[i] <= l[i - 1]:
			i -= 1
		if i == 0:
			return -1
		else:
			i -= 1
			j = x - 1
			while i < j and l[i] >= l[j]:
				j -= 1
			while l[j - 1] == l[j]:
				j -= 1
			(l[i], l[j]) = (l[j], l[i])
			return ''.join(l)


class Solution:

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