Given a non-negative number N. The task is to apply at most one swap operation on the number N so that the result is the smallest possible number.
Note: Input and Output should not contain leading zeros.
Example 1:
Input: N = "9625635"
Output: "2695635"
Explanation: Swapped the digits 9 and 2.
Example 2:
Input: N = "1205763"
Output: "1025763"
Explanation: Swapped the digits 0 and 2.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function smallestNumber() which takes the string as inputs and returns the answer.
Expected Time Complexity: O(|N|)
Expected Auxiliary Space: O(|N|)
Constraints:
1 ≤ |N| ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def smallestNumber(self, num):
        # code here

Solutions:
class Solution:

	def smallestNumber(self, num):
		num = list(num)
		str_num = []
		for e in num:
			str_num.append(e)
		n = len(num)
		rightMin = [0] * n
		right = 0
		rightMin[n - 1] = -1
		right = n - 1
		for i in range(n - 2, -1, -1):
			if num[i] >= num[right]:
				rightMin[i] = right
			else:
				rightMin[i] = -1
				right = i
		small = -1
		mini = 25555555555
		for i in range(1, n):
			if str_num[i] == '0':
				for j in range(n - 1, -1, -1):
					if mini > int(str_num[j]) and str_num[j] != '0':
						small = j
						mini = int(str_num[j])
				(str_num[0], str_num[small]) = (str_num[small], str_num[0])
				break
		for i in range(0, n):
			if i != 0:
				if rightMin[i] != -1 and num[i] != num[rightMin[i]]:
					(num[i], num[rightMin[i]]) = (num[rightMin[i]], num[i])
					break
			elif rightMin[i] != -1 and num[rightMin[i]] != '0' and (num[i] != num[rightMin[i]]):
				(num[i], num[rightMin[i]]) = (num[rightMin[i]], num[i])
				break
		ans1 = ''.join(num)
		ans2 = ''.join(str_num)
		if ans1 < ans2:
			return ans1
		else:
			return ans2