Find Maximum number possible by doing at-most K swaps Hard 0 attempts
GeeksforGeeks ↗

Find Maximum number possible by doing at-most K swaps

Hard BacktrackingRecursion GeeksforGeeks

You're given a number represented as a string num, along with an integer k. By swapping any two digits within the string, at most k times, determine the largest possible numeric value you can form.

Edge cases: When k = 0, the original number is returned unchanged. The digits may already be sorted in descending order. The maximum digit may appear more than once.

Input Format
Implement findMaximumNum(num, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
num = "1234567"
k = 4
Output
"7654321"

Example 2

Input
num = "1234"
k = 1
Output
"4231"

Example 3

Input
num = "1234"
k = 0
Output
"1234"
Constraints
  • 0 <= k <= 10
  • 1 <= num.length <= 30
  • num contains decimal digits.
Test Cases (3)
Case 1
Args: ["1234567",4] Expected: "7654321"
Case 2
Args: ["1234",1] Expected: "4231"
Case 3
Args: ["1234",0] Expected: "1234"
Topics
BacktrackingRecursion

Approach: Backtracking

For each position from left to right, find the maximum digit in the remaining positions. If it's larger than the current digit, swap them and recurse with k - 1. Track the global maximum found so far. Prune by skipping positions where the digit is already the max possible.

javascript
function findMaximumNum(num, k) {
  let maxNum = num.split('');

  function solve(arr, k, idx) {
    if (k === 0 || idx === arr.length) return;

    let maxDigit = arr[idx];
    for (let i = idx + 1; i < arr.length; i++) {
      if (arr[i] > maxDigit) maxDigit = arr[i];
    }

    if (maxDigit === arr[idx]) {
      solve(arr, k, idx + 1);
      return;
    }

    for (let i = arr.length - 1; i > idx; i--) {
      if (arr[i] === maxDigit) {
        [arr[idx], arr[i]] = [arr[i], arr[idx]];
        if (arr.join('') > maxNum.join('')) {
          maxNum = [...arr];
        }
        solve(arr, k - 1, idx + 1);
        [arr[idx], arr[i]] = [arr[i], arr[idx]];
      }
    }
  }

  solve(num.split(''), k, 0);
  return maxNum.join('');
}

Time Complexity: O(n! / (n-k)!) in the worst case, but pruning makes it much faster in practice

Space Complexity: O(n) for recursion stack

Saved in this browser only. Private to you.

JavaScript