Maximum number by doing at most K swaps

Medium

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"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}