MediumBacktrackingAI interview only
Largest Number In K Swaps
Asked atamazonmicrosoftadobe
01 · Problem
You are given a string s of digits representing a positive integer, and an integer k. In one swap you may exchange the digits at any two positions of the string.
Using at most k swaps, return the largest number that can be produced, as a string of the same length. You do not have to use all k swaps.
02 · Examples
Example 01
Input
s = "1234567", k = 4
Output
"7654321"
Swap 1<->7, 2<->6 and 3<->5. Three swaps already give 7654321, the largest arrangement of these digits.
Example 02
Input
s = "3435335", k = 3
Output
"5543333"
Bring a 5 to the front, then another 5 to the second position, then the 4 to the third position: 5543333.
Example 03
Input
s = "1034", k = 2
Output
"4301"
Swap 1<->4 to get 4031, then 0<->3 to get 4301.
03 · Constraints
- 01`1 <= s.length <= 12`
- 02`s` consists of digits `0`-`9` and does not start with `0`
- 03`1 <= k <= 5`
04 · Optimal complexity
- Time
- O(n^k)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.