Smallest Code by Neighbor Swaps

Hard

You are given a string of digits code, the decimal form of a large integer with no leading zeros, and an integer swaps. You may swap two **adjacent** digits at most swaps times. Return the smallest number you can obtain this way, also as a string. Leading zeros are allowed in the answer: strings of equal length are compared as numbers.

Example 1

code='5317', swaps=3 → '1357'

Two swaps bring the 1 to the front: "1537". The third swaps 5 and 3: "1357".

Example 2

code='2005', swaps=2 → '0025'

One swap brings the first zero to the front: "0205". The last swap moves the second zero to position 1: "0025". Leading zeros are allowed in the answer.

Example 3

code='1234', swaps=50 → '1234'

The digits are already in increasing order, so it is best to leave them alone.

Constraints

1 ≤ code.length ≤ 3 · 10⁴
code consists of digits and does not start with zero (unless it is a single character)
1 ≤ swaps ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Binary Indexed Tree Segment Tree String

Similar problems

Palindrome by Adjacent Swaps Hard Deal Out From the Lowest Card Hard Does the Text Fit the Pattern Hard City Block Outline Hard Smaller Values to the Right Hard

Input

code='5317', swaps=3

Expected

'1357'

Run checks the first 3 tests in your browser. Submit checks all 103 tests on the server, hidden ones included.