Given a number K and string str of digits denoting a positive integer, build the largest number possible by performing swap operations on the digits of str at most K times.
Example 1:
Input:
K = 4
str = "1234567"
Output:
7654321
Explanation:
Three swaps can make the
input 1234567 to 7654321, swapping 1
with 7, 2 with 6 and finally 3 with 5
Example 2:
Input:
K = 3
str = "3435335"
Output:
5543333
Explanation:
Three swaps can make the input
3435335 to 5543333, swapping 3 
with 5, 4 with 5 and finally 3 with 4 
Your task:
You don't have to read input or print anything. Your task is to complete the function findMaximumNum() which takes the string and an integer as input and returns a string containing the largest number formed by perfoming the swap operation at most k times.
Expected Time Complexity: O(n!/(n-k)!) , where n = length of input string
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ |str| ≤ 30
1 ≤ K ≤ 10

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:
    
    #Function to find the largest number after k swaps.
    def findMaximumNum(self,s,k):
        #code here


Solutions:
class Solution:

	def solve(self, string, k, index, maxi):
		if k <= 0 or index >= len(string) - 1:
			return
		max_ = string[index]
		for i in range(index + 1, len(string)):
			if int(max_) < int(string[i]):
				max_ = string[i]
		if string[index] != max_:
			k -= 1
		for i in range(index, len(string)):
			if max_ == string[i]:
				(string[index], string[i]) = (string[i], string[index])
				new_str = ''.join(string)
				if int(new_str) > int(maxi[0]):
					maxi[0] = new_str
				self.solve(string, k, index + 1, maxi)
				(string[index], string[i]) = (string[i], string[index])

	def findMaximumNum(self, s, k):
		maxi = [s]
		string = [char for char in s]
		index = 0
		self.solve(string, k, index, maxi)
		return maxi[0]


class Solution:

	def findMaximumNum(self, s, k):
		maxi = [s]
		string = [char for char in s]
		idx = 0
		self.findMaxNumUtil(string, k, idx, maxi)
		return maxi[0]

	def findMaxNumUtil(self, string, k, idx, maxi):
		if k <= 0 or idx >= len(string) - 1:
			return
		max_in_str = string[idx]
		for m in range(idx + 1, len(string)):
			if int(string[m]) > int(max_in_str):
				max_in_str = string[m]
		if string[idx] != max_in_str:
			k -= 1
		for i in range(idx, len(string)):
			if string[i] == max_in_str:
				(string[idx], string[i]) = (string[i], string[idx])
				new_str = ''.join(string)
				if int(new_str) > int(maxi[0]):
					maxi[0] = new_str
				self.findMaxNumUtil(string, k, idx + 1, maxi)
				(string[idx], string[i]) = (string[i], string[idx])


class Solution:

	def findMaximumNum(self, s, k):
		N = len(s)
		input = list(s)
		return self.permutateBetter(input, s, k, 0, N)

	def permutateBetter(self, input, s, k, idx, N):
		if k == 0 or idx == N:
			return s
		maxm = input[idx]
		for v in range(idx + 1, N):
			maxm = max(maxm, input[v])
		if maxm != input[idx]:
			k -= 1
		for j in range(idx, N):
			if input[j] == maxm:
				(input[idx], input[j]) = (input[j], input[idx])
				s = max(s, ''.join(input))
				s = self.permutateBetter(input, s, k, idx + 1, N)
				(input[idx], input[j]) = (input[j], input[idx])
		return s


class Solution:

	def findMaximumNum(self, s, k):

		def backtrack(string, k, start):
			nonlocal maxi
			if k <= 0 or start >= len(string) - 1:
				return
			cur_digit = string[start]
			for i in range(start + 1, len(string)):
				if cur_digit < string[i]:
					cur_digit = string[i]
			if cur_digit != string[start]:
				k -= 1
			for i in range(start, len(string)):
				if cur_digit == string[i]:
					(string[i], string[start]) = (string[start], string[i])
					new_string = ''.join(string)
					if maxi < new_string:
						maxi = new_string
					backtrack(string, k, start + 1)
					(string[i], string[start]) = (string[start], string[i])
		maxi = s
		string = [char for char in s]
		backtrack(string, k, 0)
		return maxi


class Solution:

	def findMaximumNum(self, s, k):

		def recursion(maxi, s, idx, k, n):
			if k == 0 or not s or idx >= n:
				return maxi
			mx = s[idx]
			for i in range(idx + 1, n):
				if int(s[i]) > int(mx):
					mx = s[i]
			if mx != s[idx]:
				k -= 1
			for i in range(idx, n):
				if s[i] == mx:
					(s[idx], s[i]) = (s[i], s[idx])
					new = ''.join(s)
					if int(new) > int(maxi[0]):
						maxi[0] = new
					recursion(maxi, s, idx + 1, k, n)
					(s[idx], s[i]) = (s[i], s[idx])
			return maxi
		maxi = [s]
		s = [char for char in s]
		n = len(s)
		maxi = recursion(maxi, s, 0, k, n)
		return maxi[0]


class Solution:

	def findMaximumNum(self, s, k):
		num = [int(x) for x in s]
		res = [int(x) for x in s]
		self.find(num, res, 0, k)
		return ''.join((str(x) for x in res))

	def find(self, num, res, index, k):
		if k == 0 or index == len(num) - 1:
			self.match(num, res)
			return
		maxdigit = 0
		for i in range(index, len(num)):
			maxdigit = max(maxdigit, num[i])
		if num[index] == maxdigit:
			self.find(num, res, index + 1, k)
			return
		for i in range(index + 1, len(num)):
			if num[i] == maxdigit:
				(num[index], num[i]) = (num[i], num[index])
				self.find(num, res, index + 1, k - 1)
				(num[index], num[i]) = (num[i], num[index])

	def match(self, num, res):
		for i in range(len(num)):
			if res[i] > num[i]:
				return
			if res[i] < num[i]:
				for j in range(len(num)):
					res[j] = num[j]
				return


class Solution:

	def findMaximumNum(self, s, k):
		sarr = list(s)
		return self.maxUtil(sarr, 0, k)

	def maxUtil(self, s, i, k):
		n = len(s)
		res = ''.join(s)
		if k == 0 or i == n:
			return res
		maxj = i
		for j in range(i + 1, n):
			if s[j] > s[i] and s[j] > s[maxj]:
				maxj = j
		if maxj != i:
			for j in range(i + 1, n):
				if s[j] == s[maxj]:
					(s[i], s[j]) = (s[j], s[i])
					res = max(res, self.maxUtil(s, i + 1, k - 1))
					(s[i], s[j]) = (s[j], s[i])
		else:
			res = max(res, self.maxUtil(s, i + 1, k))
		return res


def findMaximumNum(string, k, maxm, ctr):
	if k == 0 or ctr >= len(string):
		return
	n = len(string)
	mx = string[ctr]
	for i in range(ctr + 1, n):
		if int(string[i]) > int(mx):
			mx = string[i]
	if mx != string[ctr]:
		k = k - 1
	for i in range(ctr, n):
		if string[i] == mx:
			(string[ctr], string[i]) = (string[i], string[ctr])
			new_str = ''.join(string)
			if int(new_str) > int(maxm[0]):
				maxm[0] = new_str
			findMaximumNum(string, k, maxm, ctr + 1)
			(string[ctr], string[i]) = (string[i], string[ctr])

class Solution:

	def findMaximumNum(self, s, k):
		maxm = [s]
		s = [char for char in s]
		findMaximumNum(s, k, maxm, 0)
		return maxm[0]


class Solution:

	def findMaximumNum(self, s, k):
		maxval = ['-1']
		n = len(s)

		def swaps(s, i, k, n):
			maxval[0] = max(maxval[0], s)
			if i >= n or k <= 0:
				return
			ind = i
			for x in range(i, n):
				if s[x] > s[ind]:
					ind = x
			ls = []
			for x in range(i, n):
				if s[x] == s[ind]:
					ls.append(x)
			for ind in ls:
				if s[ind] > s[i]:
					t = list(s)
					(t[i], t[ind]) = (t[ind], t[i])
					swaps(''.join(t), i + 1, k - 1, n)
				else:
					swaps(s, i + 1, k, n)
			return
		swaps(s, 0, k, n)
		return maxval[0]


class Solution:

	def swap(self, str, i, j):
		s = list(str)
		(s[i], s[j]) = (s[j], s[i])
		return ''.join(s)

	def findMaximumNum(self, s, k):
		import sys
		sys.setrecursionlimit(10000000)
		result = ['']
		self.findMax(0, s, k, result)
		return result[0]

	def findMax(self, index, s, k, result):
		if k == 0 or index >= len(s) - 1:
			return
		maxchar = s[index]
		for i in range(index + 1, len(s)):
			if s[i] > maxchar:
				maxchar = s[i]
		if maxchar != s[index]:
			k -= 1
		for j in range(len(s) - 1, index - 1, -1):
			if s[j] == maxchar:
				s = self.swap(s, index, j)
				if s > result[0]:
					result[0] = s[:]
				self.findMax(index + 1, s, k, result)
				s = self.swap(s, index, j)


class Solution:

	def findMaximumNum(self, S, K):
		from collections import Counter
		S = [ord(c) - 48 for c in S]
		N = len(S)
		CNT = Counter(S)
		ans = S.copy()
		(i2v, tot) = ([-1] * N, 0)
		for i in reversed(range(10)):
			L = CNT[i]
			i2v[tot:tot + L] = [i] * L
			tot += L

		def _solve(i, K):
			if K <= 0 or i >= N:
				if S > ans:
					ans[:] = S
				return
			v = i2v[i]
			if v == S[i]:
				_solve(i + 1, K)
				return
			for j in reversed(range(i + 1, N)):
				if S[j] == v:
					(S[j], S[i]) = (S[i], S[j])
					_solve(i + 1, K - 1)
					(S[j], S[i]) = (S[i], S[j])
		_solve(0, K)
		return ''.join((str(v) for v in ans))


class Solution:

	def findMaximumNum(self, S, K):
		from bisect import insort
		N = len(S)
		S = [ord(c) - 48 for c in S]
		ans = S.copy()
		v2ix = [[] for _ in range(10)]
		for (i, v) in enumerate(S):
			v2ix[v].append(i)
		(i2v, tot) = ([-1] * N, 0)
		for i in reversed(range(10)):
			L = len(v2ix[i])
			i2v[tot:tot + L] = [i] * L
			tot += L

		def _solve(i, K):
			if K <= 0 or i >= N:
				if S > ans:
					ans[:] = S
				return
			v = i2v[i]
			if v == S[i]:
				_solve(i + 1, K)
				return
			ixs = v2ix[v].copy()
			for j in reversed(ixs):
				if j <= i:
					break
				v2ix[v].remove(j)
				insort(v2ix[v], i)
				v2ix[S[i]].remove(i)
				insort(v2ix[S[i]], j)
				(S[j], S[i]) = (S[i], S[j])
				_solve(i + 1, K - 1)
				(S[j], S[i]) = (S[i], S[j])
				v2ix[S[i]].remove(j)
				insort(v2ix[S[i]], i)
				v2ix[v].remove(i)
				insort(v2ix[v], j)
		_solve(0, K)
		return ''.join((str(v) for v in ans))


class Solution:

	def solve(self, idx, arr, k, n, largest):
		largest[0] = max(largest[0], ''.join((i for i in arr)))
		if k == 0 or idx >= n:
			return
		maxc = max(arr[idx:])
		for i in range(idx + 1, n):
			if arr[i] == maxc and arr[idx] != maxc:
				(arr[i], arr[idx]) = (arr[idx], arr[i])
				self.solve(idx + 1, arr, k - 1, n, largest)
				(arr[idx], arr[i]) = (arr[i], arr[idx])
		self.solve(idx + 1, arr, k, n, largest)

	def findMaximumNum(self, s, k):
		arr = list(s)
		n = len(arr)
		largest = [s]
		self.solve(0, arr, k, n, largest)
		return largest[0]


class Solution:

	def helper(self, s, ans, i, k, n):
		if k == 0 or i >= n:
			return
		s = list(s)
		mx = max(s[i:])
		if mx != s[i]:
			k -= 1
		for x in range(i, n):
			if s[x] == mx:
				(s[i], s[x]) = (s[x], s[i])
				ans[0] = max(ans[0], ''.join(s))
				self.helper(''.join(s), ans, i + 1, k, n)
				(s[i], s[x]) = (s[x], s[i])

	def findMaximumNum(self, s, k):
		ans = ['']
		self.helper(s, ans, 0, k, len(s))
		return ans[0]


class Solution:

	def findMaximumNum(self, s, k):
		temp = [i for i in s]
		self.m = list(temp)

		def sol(temp, k, idx):
			n = len(temp)
			if k == 0 or idx == n - 1:
				return
			max_elm = int(temp[idx])
			curr = int(temp[idx])
			for i in range(idx + 1, n):
				max_elm = max(max_elm, int(temp[i]))
			if curr != max_elm:
				k = k - 1
			for i in range(idx, n):
				if int(temp[i]) == max_elm:
					(temp[idx], temp[i]) = (temp[i], temp[idx])
					if int(''.join(self.m)) < int(''.join(temp)):
						self.m = list(temp)
					sol(temp, k, idx + 1)
					(temp[idx], temp[i]) = (temp[i], temp[idx])
			return self.m
		return ''.join(sol(temp, k, 0))


class Solution:

	def findMaximumNum(self, s, k):
		s = list(s)
		n = len(s)
		self.maxi = -float('inf')

		def recsol(k, i):
			if k == 0:
				return
			if i < n:
				mx = s[i]
			for j in range(i + 1, n):
				if j < n and int(s[j]) > int(mx):
					mx = s[j]
			if i < n and mx != s[i]:
				k = k - 1
			for j in range(i, n):
				if s[j] == mx:
					(s[i], s[j]) = (s[j], s[i])
					self.maxi = max(self.maxi, int(''.join(s)))
					recsol(k, i + 1)
					(s[i], s[j]) = (s[j], s[i])
		recsol(k, 0)
		return self.maxi


class Solution:

	def findMaximumNum(self, s, k):
		st = list(s)
		self.m = s

		def solve(st, i, k):
			if i >= len(st) or k == 0:
				return
			mxelm = st[i]
			for j in range(i + 1, len(st)):
				if int(st[j]) > int(mxelm):
					mxelm = st[j]
			if mxelm != st[i]:
				k -= 1
			for j in range(i, len(st)):
				if st[j] == mxelm:
					(st[j], st[i]) = (st[i], st[j])
					new = ''.join(st)
					if int(new) > int(self.m):
						self.m = new
					solve(st, i + 1, k)
					(st[j], st[i]) = (st[i], st[j])
		solve(st, 0, k)
		return self.m


class Solution:

	def findMaximumNum(self, s, k):
		s = list(s)
		n = len(s)
		maximum = -float('inf')

		def backtrack(k, idx):
			nonlocal maximum
			if k == 0 or idx == n:
				return
			curr_max = s[idx]
			for j in range(idx + 1, n):
				if j < n and int(s[j]) > int(curr_max):
					curr_max = s[j]
			if idx < n and curr_max != s[idx]:
				k -= 1
			for j in range(idx, n):
				if s[j] == curr_max:
					(s[idx], s[j]) = (s[j], s[idx])
					maximum = max(maximum, int(''.join(s)))
					backtrack(k, idx + 1)
					(s[idx], s[j]) = (s[j], s[idx])
		backtrack(k, 0)
		return maximum


class Solution:

	def findMaximumNum(self, s, k):
		maxi = [float('-inf')]
		arr = [char for char in s]

		def swap(i, j, arr):
			(arr[i], arr[j]) = (arr[j], arr[i])

		def helper(i, arr, k):
			if k == 0 or i == len(arr):
				return
			maxChar = arr[i]
			for idx in range(i + 1, len(arr)):
				if int(maxChar) < int(arr[idx]):
					maxChar = arr[idx]
			if maxChar != arr[i]:
				k -= 1
			for idx in range(len(arr) - 1, i - 1, -1):
				if arr[idx] == maxChar:
					swap(idx, i, arr)
					maxi[0] = max(maxi[0], int(''.join(arr)))
					helper(i + 1, arr, k)
					swap(idx, i, arr)
		helper(0, arr, k)
		return maxi[0]


class Solution:

	def match(self, num, res):
		for i in range(len(num)):
			if res[i] > num[i]:
				return
			if res[i] < num[i]:
				for i in range(len(num)):
					res[i] = num[i]
				return

	def setDigit(self, num, index, res, k):
		if k == 0 or index == len(num) - 1:
			self.match(num, res)
			return
		maxDigit = 0
		for i in range(index, len(num)):
			maxDigit = max(maxDigit, num[i])
		if num[index] == maxDigit:
			self.setDigit(num, index + 1, res, k)
			return
		for i in range(index + 1, len(num)):
			if num[i] == maxDigit:
				(num[index], num[i]) = (num[i], num[index])
				self.setDigit(num, index + 1, res, k - 1)
				(num[index], num[i]) = (num[i], num[index])

	def findMaximumNum(self, s, k):
		num = [int(x) for x in s]
		res = [int(x) for x in s]
		self.setDigit(num, 0, res, k)
		return ''.join((str(x) for x in res))


from collections import defaultdict

class Solution:

	def findMaximumNum(self, s, k):
		n = len(s)
		arr = [int(c) for c in s]
		ans = arr.copy()

		def helper(i):
			nonlocal k, arr, n, ans
			if ans < arr:
				ans = arr.copy()
			if k == 0:
				return
			if i == n - 1:
				return
			maxEle = max(arr[i + 1:])
			for j in range(i + 1, n):
				if arr[j] == maxEle:
					(arr[i], arr[j]) = (arr[j], arr[i])
					k -= 1
					helper(i + 1)
					k += 1
					(arr[i], arr[j]) = (arr[j], arr[i])
			if i + 1 < n:
				helper(i + 1)
		try:
			helper(0)
		except Exception as err:
			print(err)
		return ''.join(map(str, ans))


class Solution:

	def findMaximumNum(self, s, k):
		mxx = [s]
		n = len(s)
		string = [x for x in s]

		def fun(string, k, mxx, idx):
			if k == 0:
				return
			n = len(string)
			if idx == n:
				return
			mx = string[idx]
			for j in range(idx + 1, n):
				if int(mx) < int(string[j]):
					mx = string[j]
			if mx != string[idx]:
				k -= 1
			for i in range(n):
				if string[i] == mx:
					(string[idx], string[i]) = (string[i], string[idx])
					new_str = ''.join((x for x in string))
					if int(new_str) > int(mxx[0]):
						mxx[0] = new_str
					fun(string, k, mxx, idx + 1)
					(string[idx], string[i]) = (string[i], string[idx])
		fun(string, k, mxx, 0)
		return mxx[0]


from collections import defaultdict

class Solution:

	def findMaximumNum(self, s, k):
		st = list(s)
		self.m = s

		def find(st, i, k):
			if i >= len(st) or k == 0:
				return
			mxelm = st[i]
			for j in range(i + 1, len(st)):
				if int(st[j]) > int(mxelm):
					mxelm = st[j]
			if mxelm != st[i]:
				k -= 1
			for j in range(i, len(st)):
				if st[j] == mxelm:
					(st[j], st[i]) = (st[i], st[j])
					new = ''.join(st)
					if int(new) > int(self.m):
						self.m = new
					find(st, i + 1, k)
					(st[j], st[i]) = (st[i], st[j])
		find(st, 0, k)
		return self.m


class Solution:

	def recursion(self, curr, s, k, n, ans):
		if k == 0 or curr >= n:
			return
		mx = max(s[curr:])
		if mx != s[curr]:
			k -= 1
		for i in range(curr, n):
			if mx == s[i]:
				(s[i], s[curr]) = (s[curr], s[i])
				if ''.join(s) > ans[-1]:
					ans[-1] = ''.join(s)
				self.recursion(curr + 1, s, k, n, ans)
				(s[i], s[curr]) = (s[curr], s[i])
		return ans[-1]

	def findMaximumNum(self, s, k):
		s = [c for c in s]
		ans = [''.join(s)]
		self.recursion(0, s, k, len(s), ans)
		return ans[-1]


class Solution:

	def findMaximumNum(self, s, k):
		s = list(s)

		def largest(ind):
			maxi = -float('inf')
			for i in range(ind, len(s)):
				if maxi < int(s[i]):
					maxi = int(s[i])
					maxind = i
			return maxind
		res = []

		def backtrack(i, k, string):
			res.append(''.join(string))
			if k == 0:
				return
			if i >= len(string):
				return
			maxind = largest(i)
			maxval = int(string[maxind])
			if i == maxind:
				backtrack(i + 1, k, string)
			else:
				for j in range(i, len(string)):
					if int(string[j]) == maxval:
						(string[j], string[i]) = (string[i], string[j])
						backtrack(i + 1, k - 1, string)
						(string[j], string[i]) = (string[i], string[j])
		backtrack(0, k, s)
		ans = list(map(int, res))
		return str(max(ans)) if ans else ''


class Solution:

	def findMaximumNum(self, s, k):
		n = len(s)
		s = list(s)
		i = 0
		count = 0

		def helper(s, count, i, k, n):
			if count == k or i >= n - 1:
				return ''.join(s)
			output = helper(s, count, i + 1, k, n)
			maxl = s[i]
			for j in range(i + 1, n):
				if s[j] >= maxl:
					maxl = s[j]
			for j in range(i + 1, n):
				if s[j] == maxl:
					(s[i], s[j]) = (s[j], s[i])
					news = helper(s, count + 1, i + 1, k, n)
					if output < news:
						output = news
					(s[j], s[i]) = (s[i], s[j])
			return output
		return helper(s, count, i, k, n)


class Solution:

	def findMaximumNum(self, s, k):

		def recurse(arr, k, i, maxi):
			if k <= 0 or i >= len(arr) - 1:
				return
			maxic = arr[i]
			for m in range(i + 1, len(arr)):
				if int(arr[m]) > int(maxic):
					maxic = arr[m]
			if arr[i] != maxic:
				k -= 1
			for idx in range(i, len(arr)):
				if arr[idx] == maxic:
					(arr[idx], arr[i]) = (arr[i], arr[idx])
					temp = ''.join(arr)
					if int(temp) > int(maxi[0]):
						maxi[0] = temp
					recurse(arr, k, i + 1, maxi)
					(arr[idx], arr[i]) = (arr[i], arr[idx])
		maxi = [s]
		arr = [char for char in s]
		recurse(arr, k, 0, maxi)
		return maxi[0]


class Solution:

	def findMaximumNum(self, s, k):
		n = len(s)
		arr = list(s)
		ans = [s]

		def rec(i, swaps):
			if i == n or swaps == k:
				ans[0] = max(ans[0], ''.join(arr))
				return
			m = arr[i]
			for j in range(i + 1, n):
				m = max(m, arr[j])
			if m == arr[i]:
				rec(i + 1, swaps)
				return
			for j in range(i + 1, n):
				if arr[j] == m:
					(arr[i], arr[j]) = (arr[j], arr[i])
					rec(i + 1, swaps + 1)
					(arr[i], arr[j]) = (arr[j], arr[i])
		rec(0, 0)
		return ans[0]


class Solution:

	def findMaximumNum(self, s, k):
		s = list(s)
		maxStr = ['']
		getMaximumNum(s, 0, 0, k, maxStr)
		ansStr = ''
		return maxStr[0]

def getGreatestNumber(s, idx):
	minVal = 0
	ans = 0
	for i in range(idx, len(s)):
		if ans <= int(s[i]):
			ans = int(s[i])
			minVal = i
	return minVal

def getLar(s, s2):
	str1 = ''.join(s)
	if str1 > s2:
		s2 = str1
	return s2

def getMaximumNum(s, idx, count, k, maxStr):
	if k == count:
		maxStr[0] = getLar(s, maxStr[0])
		return
	if idx == len(s):
		maxStr[0] = getLar(s, maxStr[0])
		return
	getIdx = getGreatestNumber(s, idx)
	if s[getIdx] != s[idx]:
		count += 1
	for i in range(len(s)):
		if s[i] == s[getIdx]:
			(s[i], s[idx]) = (s[idx], s[i])
			getMaximumNum(s, idx + 1, count, k, maxStr)
			(s[i], s[idx]) = (s[idx], s[i])


class Solution:

	def findMaximumNum(self, s, k):
		arr = list(s)
		ans = [s]

		def rec(i, c):
			if i == len(s) or c == k:
				ans[0] = max(ans[0], ''.join(arr))
				return
			maxch = max([ord(ch) for ch in arr[i:]])
			if ord(arr[i]) == maxch:
				rec(i + 1, c)
				return
			for j in range(i + 1, len(s)):
				if ord(arr[j]) == maxch:
					(arr[i], arr[j]) = (arr[j], arr[i])
					rec(i + 1, c + 1)
					(arr[i], arr[j]) = (arr[j], arr[i])
		rec(0, 0)
		return ans[0]


class Solution:

	def findMaximumNum(self, s, k):

		def swap(arr, i, j):
			(arr[i], arr[j]) = (arr[j], arr[i])

		def solve(idx, k, n):
			if k == 0 or idx >= n:
				return
			rmax = arr[idx]
			for j in range(idx + 1, n):
				if arr[j] > rmax:
					rmax = arr[j]
			if rmax == arr[idx]:
				solve(idx + 1, k, n)
				return
			for j in range(idx, n):
				if arr[j] == rmax:
					swap(arr, idx, j)
					temp = ''.join(arr)
					ans[0] = max(ans[0], temp)
					solve(idx + 1, k - 1, n)
					swap(arr, idx, j)
		arr = list(s)
		n = len(arr)
		ans = [s]
		solve(0, k, n)
		return ans[0]


class Solution:

	def findMaximumNum(self, string, k):
		self.result = string
		n = len(string)
		i = 0
		self.solve(i, k, string, n)
		return self.result

	def solve(self, i, k, string, n):
		if k == 0 or i >= n:
			return None
		maxch = string[i]
		for ch in string[i + 1:]:
			maxch = max(ch, maxch)
		if maxch != string[i]:
			k -= 1
		for j in range(i, n):
			if string[j] == maxch:
				swapped = self.swap(i, j, string, n)
				self.result = max(swapped, self.result)
				self.solve(i + 1, k, swapped, n)
		return False

	def swap(self, i, j, string, n):
		if i == j:
			return string
		swapped = string[:i] + string[j] + string[i + 1:j] + string[i] + string[j + 1:]
		return swapped


class Solution:

	def findMaximumNum(self, s, k):
		ans = int(s)
		s = list(s)
		s = list(map(int, s))

		def helper(start, s, k):
			nonlocal ans
			if k == 0 or start == len(s):
				ta = int(''.join(list(map(str, s))))
				ans = max(ta, ans)
				return
			biggest_index = [start]
			pointer = start + 1
			while pointer < len(s):
				if s[pointer] >= s[biggest_index[-1]]:
					if s[biggest_index[-1]] != s[pointer]:
						biggest_index = []
					biggest_index.append(pointer)
				pointer += 1
			noswap = True
			for big in biggest_index:
				if big != start and s[big] != s[start]:
					noswap = False
					(s[start], s[big]) = (s[big], s[start])
					helper(start + 1, s, k - 1)
					(s[start], s[big]) = (s[big], s[start])
			if noswap and k:
				helper(start + 1, s, k)
		helper(0, s, k)
		return ans


class Solution:

	def findMaximumNum(self, s, k):

		def swap(strg, k, ans, ind):
			if k <= 0 or ind >= n - 1:
				return
			maxchar = int(strg[ind])
			for i in range(ind + 1, n):
				maxchar = max(maxchar, int(strg[i]))
			if maxchar != int(strg[ind]):
				k -= 1
			for i in range(ind, n):
				if int(strg[i]) == int(maxchar):
					(strg[i], strg[ind]) = (strg[ind], strg[i])
					new_strg = ''.join(strg)
					ans[0] = max(int(ans[0]), int(new_strg))
					swap(strg, k, ans, ind + 1)
					(strg[i], strg[ind]) = (strg[ind], strg[i])
		n = len(s)
		ans = [s]
		s = [i for i in s]
		swap(s, k, ans, 0)
		return ans[0]


class Solution:

	def findMaximumNum(self, s, k):
		lis = []
		for i in s:
			lis.append(int(i))
		n = len(lis)
		ans = [s]

		def rec(ind, n, k, lis, ans):
			if ind == n or k == 0:
				tem = ''
				for i in lis:
					tem += str(i)
				if ans[0] < tem:
					ans[0] = tem
				return
			rec(ind + 1, n, k, lis, ans)
			mx = lis[ind]
			for j in range(ind + 1, n):
				if mx < lis[j]:
					mx = lis[j]
			if mx == lis[ind]:
				return
			for j in range(ind + 1, n):
				if lis[j] == mx:
					(lis[ind], lis[j]) = (lis[j], lis[ind])
					rec(ind + 1, n, k - 1, lis, ans)
					(lis[ind], lis[j]) = (lis[j], lis[ind])
		rec(0, n, k, lis, ans)
		return ans[0]


class Solution:

	def findMaximumNum(self, s, k):
		s = list(s)
		self.ans = '0'

		def swap(s, k, left, t):
			if t == k or left >= len(s):
				tmp = ''.join(s)
				if tmp > self.ans:
					self.ans = tmp
			if left < len(s) and t < k:
				cur_max = s[left]
				ind = left
				flag = 0
				for i in range(left + 1, len(s)):
					if s[i] > cur_max:
						cur_max = s[i]
						ind = i
						flag = 1
				if flag == 1:
					for j in range(left + 1, len(s)):
						if s[j] == cur_max:
							(s[left], s[j]) = (s[j], s[left])
							left += 1
							t += 1
							swap(s, k, left, t)
							left -= 1
							t -= 1
							(s[left], s[j]) = (s[j], s[left])
				else:
					swap(s, k, left + 1, t)
		left = 0
		t = 0
		swap(s, k, left, t)
		return self.ans


class Solution:

	def findMaximumNum(self, s, k):
		m = [s]
		sr = [char for char in s]
		i = 0
		self.maxnow(sr, k, i, m)
		return m[0]

	def maxnow(self, sr, k, i, m):
		if k <= 0 or i >= len(sr) - 1:
			return
		maxx = sr[i]
		for j in range(i + 1, len(sr)):
			if int(sr[j]) > int(maxx):
				maxx = sr[j]
		if sr[i] != maxx:
			k -= 1
		for l in range(i, len(sr)):
			if sr[l] == maxx:
				(sr[i], sr[l]) = (sr[l], sr[i])
				str1 = ''.join(sr)
				if int(str1) > int(m[0]):
					m[0] = str1
				self.maxnow(sr, k, i + 1, m)
				(sr[i], sr[l]) = (sr[l], sr[i])


class Solution:

	def find_max(self, s, k, num, i=0):
		if k == 0 or i >= len(s):
			return
		n = len(s)
		mx = s[i]
		for j in range(i + 1, n):
			if int(s[j]) > int(mx):
				mx = s[j]
		if mx != s[i]:
			k = k - 1
		for j in range(i, n):
			if s[j] == mx:
				(s[i], s[j]) = (s[j], s[i])
				new_str = ''.join(s)
				if int(new_str) > int(num[0]):
					num[0] = new_str
				self.find_max(s, k, num, i + 1)
				(s[i], s[j]) = (s[j], s[i])

	def findMaximumNum(self, s, k):
		num = [s]
		s = list(s)
		self.find_max(s, k, num)
		return num[0]


class Solution:

	def findMaximumNum(self, s, k):

		def eval_(s):
			count = 0
			for c in s:
				if c == '0':
					count += 1
				else:
					break
			return eval(s[count:])
		max_num = [eval_(s)]

		def helper(s, start, k):
			if k == 0:
				max_num[0] = max(eval_(s), max_num[0])
				return
			max_num[0] = max(eval_(s), max_num[0])
			for i in range(start, len(s) - 1):
				max_ind = i
				for j in range(i + 1, len(s)):
					if int(s[j]) > int(s[max_ind]):
						max_ind = j
				if max_ind == i:
					continue
				for jj in range(i + 1, len(s)):
					if s[jj] != s[max_ind]:
						continue
					j = jj
					new_s = s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
					if new_s[0] == '0':
						continue
					helper(new_s, i + 1, k - 1)
		helper(s, 0, k)
		return max_num[0]


class Solution:

	def findMaximumNum(self, s, k):

		def func(i, j, s1, k):
			if i == n or j == m or k == 0:
				return s1
			if s1[i] == store[j]:
				return func(i + 1, j + 1, s1, k)
			key = ''
			for ind in range(0, n):
				key += str(s1[ind])
			key += '#' + str(k)
			if key in cache:
				return cache[key]
			res = []
			for ind in dic[store[j]]:
				(s1[ind], s1[i]) = (s1[i], s1[ind])
				dic[s1[i]].remove(ind)
				dic[s1[ind]].remove(i)
				dic[s1[ind]].append(ind)
				dic[s1[ind]].sort()
				temp = list(func(i + 1, j + 1, s1, k - 1))
				dic[s1[ind]].remove(ind)
				dic[s1[i]].append(ind)
				dic[s1[ind]].append(i)
				dic[s1[i]].sort()
				dic[s1[ind]].sort()
				(s1[ind], s1[i]) = (s1[i], s1[ind])
				res = res if res > temp else temp
			cache[key] = res
			return res
		s1 = list(map(int, s))
		n = len(s1)
		dic = {}
		for i in range(0, n):
			if s1[i] in dic:
				dic[s1[i]].append(i)
			else:
				dic[s1[i]] = [i]
		store = sorted(s1, reverse=1)
		m = len(store)
		cache = {}
		ans = func(0, 0, s1, k)
		res = ''
		for i in range(0, n):
			res += str(ans[i])
		return res


class Solution:

	def findMaximumNum(self, s, k):

		def f(arr, start, k):
			if k == 0:
				return
			if start == len(arr):
				return
			maximum = max(arr[start:len(arr)])
			if arr[start] != maximum:
				k -= 1
			for i in range(start, len(arr)):
				if arr[i] == maximum:
					(arr[start], arr[i]) = (arr[i], arr[start])
					newNo = int(''.join([str(ch) for ch in arr]))
					if newNo > self.maximumNo:
						self.maximumNo = newNo
					f(arr, start + 1, k)
					(arr[start], arr[i]) = (arr[i], arr[start])
		arr = [int(ch) for ch in s]
		self.maximumNo = int(''.join([str(ch) for ch in arr]))
		f(arr, 0, k)
		return self.maximumNo


class Solution:

	def findMaximumNum(self, s, k):
		maxi = [int(s)]
		idx = 0
		chars = [char for char in s]
		self.findMaxUtil(chars, idx, k, maxi)
		return maxi[0]

	def findMaxUtil(self, s, idx, k, maxi):
		if idx > len(s) - 1 or k <= 0:
			return
		max_val = s[idx]
		for i in range(idx + 1, len(s)):
			if s[i] > max_val:
				max_val = s[i]
		if max_val != s[idx]:
			k -= 1
		for i in range(idx, len(s)):
			if s[i] == max_val:
				(s[idx], s[i]) = (s[i], s[idx])
				new_word = ''.join(s)
				if int(new_word) > maxi[0]:
					maxi[0] = int(new_word)
				self.findMaxUtil(s, idx + 1, k, maxi)
				(s[idx], s[i]) = (s[i], s[idx])


class Solution:

	def findMaximumNum(self, s, k):

		def fun(a, k, ans):
			if a == []:
				return int(ans)
			maxi = max(a)
			idx = a.index(maxi)
			res = 0
			if idx != 0 and k != 0:
				for i in range(len(a)):
					if a[i] == maxi:
						(a[0], a[i]) = (a[i], a[0])
						res = max(res, fun(a[1:], k - 1, ans + str(a[0])))
						(a[0], a[i]) = (a[i], a[0])
			else:
				return fun(a[1:], k, ans + str(a[0]))
			return res
		a = []
		for i in s:
			a.append(i)
		return fun(a, k, '')


class Solution:

	def helper(self, num, k, ans, ind):
		n = len(num)
		if k <= 0 or ind >= n - 1:
			return
		maxm = num[ind]
		for i in range(ind + 1, n):
			if int(maxm) < int(num[i]):
				maxm = num[i]
		if maxm != num[ind]:
			k -= 1
		for i in range(ind, n):
			if num[i] == maxm:
				(num[i], num[ind]) = (num[ind], num[i])
				temp = ''.join(num)
				if int(temp) > int(ans[0]):
					ans[0] = temp
				self.helper(num, k, ans, ind + 1)
				(num[i], num[ind]) = (num[ind], num[i])

	def findMaximumNum(self, s, k):
		num = list(s)
		ans = [s]
		self.helper(num, k, ans, 0)
		return ans[0]


class Solution:

	def findMaximumNum(self, s, k):
		nums = [char for char in s]
		idx = 0
		maxi = [s]
		self.maxUtil(nums, idx, k, maxi)
		return maxi[0]

	def maxUtil(self, nums, idx, k, maxi):
		if idx > len(nums) - 1 or k <= 0:
			return
		maximum_val = nums[idx]
		for i in range(idx + 1, len(nums)):
			if nums[i] > maximum_val:
				maximum_val = nums[i]
		if maximum_val != nums[idx]:
			k -= 1
		for i in range(idx, len(nums)):
			if nums[i] == maximum_val:
				(nums[idx], nums[i]) = (nums[i], nums[idx])
				new_string = ''.join(nums)
				if int(new_string) > int(maxi[0]):
					maxi[0] = int(new_string)
				self.maxUtil(nums, idx + 1, k, maxi)
				(nums[idx], nums[i]) = (nums[i], nums[idx])


import collections, sys
sys.setrecursionlimit(int(1000000.0))

class Solution:

	def findMaximumNum(self, s, k):
		stl = list(map(int, s))
		res = float('-inf')

		def soln(i, st, lim):
			if i == len(s) or not lim:
				nonlocal res
				res = max(res, int(''.join(map(str, st))))
				return
			mx = float('-inf')
			temp = collections.defaultdict(lambda : list())
			for k in range(i + 1, len(st)):
				if st[k] > mx:
					mx = st[k]
					temp[mx].append(k)
				elif st[k] == mx:
					temp[mx].append(k)
			if mx == float('inf') or mx <= st[i]:
				soln(i + 1, st, lim)
			else:
				for ix in temp[mx]:
					(st[ix], st[i]) = (st[i], st[ix])
					soln(i + 1, st, lim - 1)
					(st[ix], st[i]) = (st[i], st[ix])
		soln(0, stl, k)
		return res


class Solution:

	def findMaximumNum(self, s, k):
		res = int(s)
		n = len(s)

		def swap(strg, i, j):
			if i == j:
				return strg
			ith = strg[i]
			jth = strg[j]
			left = strg[0:i]
			middle = strg[i + 1:j]
			right = strg[j + 1:]
			return left + jth + middle + ith + right

		def solve(strg, n, k, ind):
			nonlocal res
			if ind >= n or k == 0:
				return
			mx = strg[ind]
			for i in range(ind + 1, n):
				mx = max(mx, strg[i])
			if mx != strg[ind]:
				k -= 1
			for i in range(n - 1, ind - 1, -1):
				if strg[i] == mx:
					strg = swap(strg, ind, i)
					if int(strg) > res:
						res = int(strg)
					solve(strg, n, k, ind + 1)
					strg = swap(strg, ind, i)
		solve(s, n, k, 0)
		return res


class Solution:

	def findMaximumNum(self, s, k):
		string = [x for x in s]
		maxn = [int(s)]

		def maxi(maxn, string, index, k):
			if k == 0 or index == len(string):
				return
			curr = string[index]
			for i in range(index + 1, len(string)):
				if string[i] > curr:
					curr = string[i]
			if curr != string[index]:
				k = k - 1
			for i in range(index, len(string)):
				if string[i] == curr:
					(string[index], string[i]) = (string[i], string[index])
					new = ''.join(string)
					if int(new) > maxn[0]:
						maxn[0] = int(new)
					maxi(maxn, string, index + 1, k)
					(string[index], string[i]) = (string[i], string[index])
		maxi(maxn, string, 0, k)
		return str(maxn[0])


class Solution:

	def findMaximumNum(self, s, k):
		mx = float('-inf')

		def find(lst, k, ind):
			nonlocal mx
			if ind >= len(lst):
				return
			sm = 0
			for i in lst:
				sm = sm * 10 + i
			if sm > mx:
				mx = sm
			if k == 0:
				return
			found = False
			for index in range(ind + 1, len(lst)):
				if lst[index] > lst[ind]:
					found = True
					(lst[index], lst[ind]) = (lst[ind], lst[index])
					find(lst, k - 1, ind + 1)
					(lst[index], lst[ind]) = (lst[ind], lst[index])
			if found == False:
				find(lst, k, ind + 1)
		l = [int(i) for i in s]
		find(l, k, 0)
		return mx