We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Difficulty: Hard

Problem Description

You are given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k times. Return the minimum integer you can obtain also as a string.

Key Insights

  • The order of digits can be changed using adjacent swaps to minimize the number.
  • The number of swaps (k) limits how far ahead we can move a digit.
  • The goal is to find the smallest digit within the range allowed by k swaps, and then swap it to the front iteratively.
  • This process must be efficient due to the potential length of the string (up to 30,000).

Space and Time Complexity

Time Complexity: O(n * k), where n is the length of the string and k is the number of allowed swaps. Space Complexity: O(n), for the storage of the result and potentially for the manipulation of the string.

Solution

The approach involves iterating through each digit in the string and for each position, finding the smallest digit that can be moved to that position using at most k swaps. We can do this by maintaining a sliding window of the next k positions and choosing the minimum digit within that range. Once we select a digit to move, we perform the necessary swaps to bring it to the current position and decrease k accordingly.

Code Solutions

def minimumInteger(num: str, k: int) -> str:
    num = list(num)
    n = len(num)
    
    for i in range(n):
        # Find the minimum digit in the range [i, min(i + k, n)]
        min_pos = i
        for j in range(i + 1, min(i + k + 1, n)):
            if num[j] < num[min_pos]:
                min_pos = j
        
        # If we found a smaller digit, we need to bring it to position i
        if min_pos != i:
            # Calculate the number of swaps needed
            swaps = min_pos - i
            if swaps <= k:
                # Perform the swaps to bring num[min_pos] to num[i]
                while min_pos > i:
                    num[min_pos], num[min_pos - 1] = num[min_pos - 1], num[min_pos]
                    min_pos -= 1
                k -= swaps
    
    return ''.join(num)
← Back to All Questions