Maximum number by doing at most K swaps
Problem
Given a number as a string, swap any two digits at most k times to make the largest possible number. Return it.
Example 1
Input: s = "1234567", k = 4 Output: "7654321"
Example 2
Input: s = "3435335", k = 3 Output: "5543333"
Also asked as: Find Maximum number possible by doing at-most K swaps
Test cases
Case 1
Input: "1234567", 4 Expected: "7654321"
Case 2
Input: "3435335", 3 Expected: "5543333"
Case 3
Input: "129814999", 4 Expected: "999984211"
Case 4
Input: "21", 1 Expected: "21"
Case 5
Input: "123", 0 Expected: "123"
View solutionHide solution1 approach
1. Backtracking — at each position bring the largest reachable digit forward
Time O(n^k) worstSpace O(n)
For each position, find the max digit to its right; try swapping it in (spending a swap) and recurse. Track the best string seen. Only swap when it actually increases the number.
function maxNumberKSwaps(numStr, k) { const digits = [...numStr]; let best = numStr; const bt = (idx, swaps) => { if (swaps === 0 || idx === digits.length) return; const maxDigit = Math.max(...digits.slice(idx).map(Number)); for (let j = digits.length - 1; j > idx; j--) { if (Number(digits[j]) === maxDigit && digits[j] !== digits[idx]) { [digits[idx], digits[j]] = [digits[j], digits[idx]]; const cur = digits.join(''); if (cur > best) best = cur; bt(idx + 1, swaps - 1); [digits[idx], digits[j]] = [digits[j], digits[idx]]; } } bt(idx + 1, swaps); // also allow not swapping at this position }; bt(0, k); return best;}