154. Maximum Number Possible With At Most K Swaps

Given a number as a string of digits and an integer k, find the largest possible number obtainable by performing at most k swaps, where each swap exchanges the digits at any two positions.

Input: The first line contains the number as a string of digits. The second line contains the integer k, the maximum number of swaps allowed. Output: Print the largest number obtainable using at most k swaps.

1 <= number of digits <= 8, 0 <= k <= 5

This differs from a GREEDY 'always swap in the biggest available digit' approach in one subtle way: since swaps are LIMITED (at most k), a greedy choice at one position might not leave enough swaps to fix a MORE valuable improvement elsewhere - backtracking explores this tradeoff properly, which greedy alone wouldn't safely handle.

Find the largest number obtainable from a string of digits using at most k swaps (each swap exchanges any two positions). Brute force: Try every possible sequence of up to k swaps directly (exploring all combinations of swap choices) - this branches combinatorially, though the small constraints here (digits <= 8, k <= 5) keep even this manageable, and the pruning technique makes it noticeably faster. Optimised: At each swap, only considering swaps that could plausibly IMPROVE the number (swapping in a strictly LARGER digit from further right) and skipping positions that already hold the best available digit prunes away many clearly-useless branches, keeping the search focused on genuinely promising swaps only.

Build on the same left-to-right, only-improving-swaps idea, but add two further prunes: among all later positions holding the maximum candidate digit for a swap, only ever try swapping with the rightmost occurrence of that digit (swapping with an earlier equal-valued occurrence can never produce a different or better result, since the digit values placed are identical either way, but using the rightmost one preserves more useful digits earlier for future swaps); and keep a memo/visited set of digit-strings already explored via different swap orders to avoid redoing identical work reached along different paths. Since n <= 8 and k <= 5, this pruned search comfortably explores only the meaningfully distinct possibilities, guaranteeing the true maximum with far fewer branches examined than the naive backtracking. Time: O(n * k * n), heavily pruned in practice Space: O(n * k)

At each remaining swap and each position (scanned left to right, since earlier/more-significant digits matter most), find the maximum digit occurring anywhere to the right; if the current digit already equals that maximum, no swap can help at this position, so move on without spending a swap. Otherwise, only branch into swaps that would strictly increase the number (swapping the current position with a later position holding a larger digit), recursing with one fewer swap remaining and skipping non-improving swaps entirely. This significantly prunes the search tree explored by brute force, since most of the n^2 candidate swaps at any given step do not actually improve the number and get discarded immediately. Time: O(n^2 * k) branches, pruned Space: O(k)

Recursively try every possible pair of positions to swap at each of the k allowed swap steps, generating every number reachable within k swaps (including doing fewer than k swaps by also considering 'stop early' at each level), and keep track of the maximum number seen across all of these fully explored branches. This is guaranteed to find the true maximum since it examines every reachable arrangement, but the branching factor of roughly n^2 choices per level compounds across up to k levels, making it explode quickly even though n and k are individually small. Time: O((n^2)^k) Space: O(k)

1. At each of the k allowed swaps, try swapping the CURRENT position with every digit further to the right that's LARGER than it, and recurse into each possibility. 2. Backtrack (undo the swap) after fully exploring each option, to try the next candidate swap. 3. Prune: if a position already holds the maximum remaining digit available, no swap involving it can possibly improve things further - skip trying swaps there.

Time: O(n^k) in the worst case (n choices per swap, up to k swaps), heavily reduced in practice by the pruning rules, given the small constraints. Space: O(n) for the current digit-string representation at each recursive level, plus O(k) for the recursion depth.

Test k = 0 (number unchanged), an 8-digit number with k = 5 (largest case, for performance), and numbers with repeated digits where a swap wouldn't change the value.

Be ready to explain the pruning rule clearly (skip positions already holding the best achievable digit) - this is what keeps the exponential search tractable within the given small constraints, and demonstrating awareness of it is a good signal.