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

Given a number as a string and an integer k, find the largest number you can produce by swapping any two digits at most k times.

Example 1:

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

Example 2:

Input: num = "3435335", k = 3
Output: "5543333"

Example 3:

Input: num = "1234", k = 1
Output: "4231"
Explanation: Swap '1' and '4' to get the maximum in one swap.

Edge cases: k = 0 returns the original number. Number already in descending order. Multiple occurrences of the maximum digit.

Sample Input
K = 4, str = "1234567"
Sample Output
"7654321"
Constraints
  • 1 <= K <= 10
  • 1 <= str.length <= 30
Test Cases
Case 1
Args: [4,"1234567"] Expected: "7654321"
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.

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