# Python Program to find Maximum number possible by doing at-most K swaps

In this tutorial, we will see how to find the maximum number possible by doing at most K swaps in the number in Python.
Consider the following examples:

```INPUT: Number=189 K=1
OUTPUT: 981
EXPLANATION: 1 is swapped with 9

INPUT: Number=198 K=2
OUTPUT: 981
EXPLANATION:
Swap 9 with 1 so the number becomes 918.
981 is the output after swapping 8 with 1.

INPUT: Number=98765 K=1
OUTPUT: 98765
EXPLANATION: No swap requirement.

INPUT: Number=139714999, K = 4
OUTPUT: 999974211
EXPLANATION:
Swap 9 with 1 so number becomes 939714991
Swap 9 with 3 so number becomes 999714391
Swap 9 with 7 so number becomes 999914371
Swap 1 with 7 so number becomes 999974311```

### Find Maximum number possible by doing at-most K swaps in Python

In this program, we consider every digit and swap it with the following digits and check if it produces the maximum number. The function is called recursively K times.

```#Strings are immutable.
#Therefore returning a new string with swapped values
def swap(string, i, j):
return (string[:i] + string[j] + string[i + 1:j] + string[i] + string[j + 1:])

#Recursive function
def Afterkswap(string, k, maxm):
# return if no swaps left
if k == 0:
return
n = len(string)
for i in range(n - 1):
for j in range(i + 1, n):
if string[i] < string[j]:
string = swap(string, i, j)
#if the returned string is greater than the current number
if string > maxm:
maxm = string
#Recursively call findMaximumNum
Afterkswap(string, k - 1, maxm)
# backtrack
string = swap(string, i, j)

# Driver Code
s= "645957321"
k = 5
maxm = [s]
Afterkswap(string, k, maxm)
print("Greatest Number after K swaps:",maxm)
```

OUTPUT

`Greatest Number after k swaps: 976554321`

Hope you liked this tutorial!