HardStringsAI interview only
Minimum Possible Integer After At Most K Adjacent Swaps On Digits
Asked atamazongoogle
01 · Problem
You are given a string num holding the digits of a very large integer and an integer k. In one move you may swap any two adjacent digits of num. You may perform at most k moves.
Return the smallest number you can obtain, as a string of the same length. Leading zeros are allowed in the result and must be kept (do not strip them).
02 · Examples
Example 01
Input
num = "5341", k = 3
Output
"1534"
Move "1" three places to the front with three swaps: 5341 -> 5314 -> 5134 -> 1534.
Example 02
Input
num = "907", k = 1
Output
"097"
One swap brings "0" to the front: "097". Leading zeros are kept.
Example 03
Input
num = "123", k = 5
Output
"123"
The digits are already in ascending order, so no swap can make the number smaller.
03 · Constraints
- 011 <= num.length <= 3 * 104
- 02num consists only of digits and has no leading zeros
- 031 <= k <= 109
04 · Optimal complexity
- Time
- O(n log n)
- 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.