Scale Engineer

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Hard
#1388Time: O(n^2), where n is the length of the input string. The outer loop runs `n` times. In each iteration, we might scan up to `n` characters and perform a string modification (delete + insert), which takes O(n) time.Space: O(n), where n is the length of the input string. This is for storing the mutable string (e.g., `StringBuilder`).
Patterns
Greedy
Data structures
StringBinary Indexed TreeSegment Tree

Prompt

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.

 

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

 

Constraints:

  • 1 <= num.length <= 3 * 104
  • num consists of only digits and does not contain leading zeros.
  • 1 <= k <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the greedy strategy in a straightforward manner. The core idea is that to form the smallest possible number, we should try to place the smallest possible digit at the most significant position (the leftmost). We repeat this process for each subsequent position.

At each step i (from left to right), we look ahead in the string for the smallest digit that we can afford to move to position i with our remaining swaps k. A digit at index j (where j > i) requires j-i adjacent swaps to be moved to position i. Therefore, we only need to search up to k positions ahead. After finding the best digit, we perform the swaps, update k, and move to the next position.

Algorithm

  • Convert the input string num to a mutable representation, like a StringBuilder or an ArrayList<Character>.
  • Iterate from i = 0 to n-1, where n is the length of the number. This loop determines the digit to be placed at index i of the result.
  • Inside the loop, find the smallest digit and its index best_j within the search window [i, min(n-1, i + k)] of the current state of the string.
  • The search window is limited to i+k because moving a digit from an index j > i+k would require more than k swaps.
  • Once the smallest digit d at index best_j is found, move it to position i. This is done by removing the character from best_j and inserting it at i.
  • The number of swaps required for this move is best_j - i. Update k by subtracting this cost.
  • If k becomes 0, no more swaps are possible. The loop will continue, but since the search window [i, i+k] will just be [i, i], it will always pick the digit at the current position i.
  • After the loop finishes, the mutable string contains the minimum possible integer. Convert it back to a string and return.

Walkthrough

We can use a mutable string representation, like Java's StringBuilder, to facilitate the operations. The algorithm proceeds as follows:

For each position i from 0 to n-1:

  1. We scan a portion of the string starting from i to find the smallest digit. The range of this scan is [i, min(n-1, i + k)]. We find the index best_j of the first occurrence of the smallest digit in this range.
  2. We then move this character from best_j to i. With a StringBuilder, this involves deleting the character at best_j and inserting it at i.
  3. The cost of this operation is best_j - i swaps. We subtract this cost from k.
  4. We continue this process until we have processed all n positions or run out of swaps (k=0).

For example, with num = "4321" and k = 4:

  • i=0: Search in "4321" (range [0, 4]). Smallest is '1' at index 3. Cost = 3-0=3. Move '1' to front. num becomes "1432", k becomes 4-3=1.
  • i=1: Search in "432" (range [1, 1+1=2]). Smallest is '3' at index 2. Cost = 2-1=1. Move '3' to index 1. num becomes "1342", k becomes 1-1=0.
  • i=2, k=0: No more swaps. The rest of the string remains as is. The final result is "1342".
class Solution {    public String minInteger(String num, int k) {        StringBuilder sb = new StringBuilder(num);        int n = num.length();        for (int i = 0; i < n && k > 0; i++) {            int bestIdx = i;            // Find the smallest digit within reach            for (int j = i + 1; j < n && j - i <= k; j++) {                if (sb.charAt(j) < sb.charAt(bestIdx)) {                    bestIdx = j;                }            }                        if (bestIdx != i) {                char c = sb.charAt(bestIdx);                sb.deleteCharAt(bestIdx);                sb.insert(i, c);                k -= (bestIdx - i);            }        }        return sb.toString();    }}

Complexity

Time

O(n^2), where n is the length of the input string. The outer loop runs `n` times. In each iteration, we might scan up to `n` characters and perform a string modification (delete + insert), which takes O(n) time.

Space

O(n), where n is the length of the input string. This is for storing the mutable string (e.g., `StringBuilder`).

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly follows the greedy logic.

Cons

  • The time complexity of O(n^2) is too slow for the given constraints (n up to 3 * 10^4), and will likely result in a 'Time Limit Exceeded' error.

Solutions

class Solution {public  String minInteger(String num, int k) {    Queue<Integer>[] pos = new Queue[10];    for (int i = 0; i < 10; ++i) {      pos[i] = new ArrayDeque<>();    }    int n = num.length();    for (int i = 0; i < n; ++i) {      pos[num.charAt(i) - '0'].offer(i + 1);    }    StringBuilder ans = new StringBuilder();    BinaryIndexedTree tree = new BinaryIndexedTree(n);    for (int i = 1; i <= n; ++i) {      for (int v = 0; v < 10; ++v) {        if (!pos[v].isEmpty()) {          Queue<Integer> q = pos[v];          int j = q.peek();          int dist = tree.query(n) - tree.query(j) + j - i;          if (dist <= k) {            k -= dist;            q.poll();            ans.append(v);            tree.update(j, 1);            break;          }        }      }    }    return ans.toString();  }} class BinaryIndexedTree {private  int n;private  int[] c;public  BinaryIndexedTree(int n) {    this.n = n;    c = new int[n + 1];  }public  void update(int x, int delta) {    while (x <= n) {      c[x] += delta;      x += lowbit(x);    }  }public  int query(int x) {    int s = 0;    while (x > 0) {      s += c[x];      x -= lowbit(x);    }    return s;  }public  static int lowbit(int x) { return x & -x; }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem