Leetcode Problem 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Leetcode Solutions

Greedy Approach with Segment Tree

  1. Initialize a segment tree to keep track of the number of elements moved to the front.
  2. Iterate over the string from left to right.
  3. For each position, attempt to place the smallest digit (0 to 9) that can be moved within the remaining number of swaps (k).
  4. Use the segment tree to find the actual index of the digit considering the shifts caused by previous swaps.
  5. If the smallest digit is within reach (i.e., it can be moved to the current position with k or fewer swaps), perform the swap and update the segment tree.
  6. Decrease k by the number of swaps used.
  7. Repeat the process until k is 0 or the entire string has been processed.
  8. Return the resulting string.
UML Thumbnail

Greedy Approach with Priority Queue

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...