# Minimum Possible Integer After at Most K Adjacent Swaps On Digits
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits)
Canonical: https://scaleengineer.com/dsa/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Binary Indexed Tree, Segment Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/image0.jpg) 

**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
## Naive Greedy Simulation
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.
**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`).
**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.
### Explanation
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"`.

```java
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();
    }
}
```
### 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.

## Optimized Greedy with Fenwick Tree
This approach uses the same greedy strategy as the naive solution but optimizes the key operations. The bottleneck in the naive approach is repeatedly scanning the string to find the best digit and calculating the cost of moving it. The indices of digits change after every move, making it hard to track.

To optimize, we can work with the *original* indices of the digits, which are static. The cost to move a digit from its original index `p` to the current front is the number of *un-used* digits currently before it. We can use a Fenwick Tree (also known as a Binary Indexed Tree, or BIT) to efficiently query this count. The BIT allows us to find the number of digits that have already been moved from indices smaller than `p` in `O(log n)` time.
**Time:** O(n log n). The main loop runs `n` times to build the result string. The inner loop over 10 digits is a constant factor. Inside, the Fenwick Tree operations (query and update) take O(log n) time. Thus, the total time is dominated by n * log(n). · **Space:** O(n), where n is the length of the input string. O(n) is used for the queues to store indices and another O(n) for the Fenwick Tree.
**Pros:** Highly efficient with O(n log n) time complexity, which passes the given constraints.; Optimal solution for this problem structure.
**Cons:** Requires knowledge of advanced data structures like Fenwick Trees or Segment Trees.; The implementation is more complex than the naive approach.
### Explanation
The algorithm is as follows:

1.  **Preprocessing:** Create a data structure (e.g., an array of queues) to store the original 0-based indices of all occurrences of each digit from '0' to '9'.
2.  **Data Structure:** Initialize a Fenwick Tree of size `n`. We will use it to keep track of digits that have been moved to the result. When we move a digit from original index `p`, we'll perform an update `ft.update(p, 1)`.
3.  **Greedy Construction:** We build the result string from left to right. For each position `i` in the result:
    a. We search for the best digit to place. We iterate through digits `d` from '0' to '9'.
    b. For each `d`, we get its earliest original index `p` from our preprocessed queues.
    c. We calculate the number of swaps needed. This is the number of digits that were originally before `p` but have *not* yet been moved. This is equal to `p - (number of moved digits with index < p)`. The second term is computed with a BIT query: `ft.query(p-1)`.
    d. Let the cost be `c = p - ft.query(p-1)`. If `c <= k`, we can afford this move. Since we are iterating from '0' to '9', the first one we can afford is the best one. 
    e. We append this digit `d` to our result, subtract `c` from `k`, remove `p` from the queue for `d`, and update the BIT to mark `p` as used.
    f. We then break and move to the next position `i+1`.

This process ensures that at each step, we make the locally optimal choice, which leads to the globally optimal solution, and we do so efficiently.

```java
class FenwickTree {
    private int[] bit;
    private int n;

    public FenwickTree(int size) {
        this.n = size;
        this.bit = new int[n + 1];
    }

    // Update value at 0-based index
    public void update(int index, int delta) {
        index++; // Convert to 1-based index
        while (index <= n) {
            bit[index] += delta;
            index += index & -index;
        }
    }

    // Query sum up to 0-based index
    public int query(int index) {
        if (index < 0) return 0;
        index++; // Convert to 1-based index
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
}

class Solution {
    public String minInteger(String num, int k) {
        int n = num.length();
        List<Queue<Integer>> positions = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            positions.add(new LinkedList<>());
        }
        for (int i = 0; i < n; i++) {
            positions.get(num.charAt(i) - '0').add(i);
        }

        StringBuilder result = new StringBuilder();
        FenwickTree ft = new FenwickTree(n);

        for (int i = 0; i < n; i++) {
            for (int d = 0; d < 10; d++) {
                if (!positions.get(d).isEmpty()) {
                    int originalIndex = positions.get(d).peek();
                    int movedCount = ft.query(originalIndex - 1);
                    int cost = originalIndex - movedCount;

                    if (cost <= k) {
                        k -= cost;
                        result.append((char)('0' + d));
                        positions.get(d).poll();
                        ft.update(originalIndex, 1);
                        break; 
                    }
                }
            }
        }
        return result.toString();
    }
}
```
### Algorithm
*   First, pre-process the input string `num` to store the original indices of each digit ('0' through '9'). A `List<Queue<Integer>>` is suitable, where `positions.get(d)` gives a queue of indices for digit `d`.
*   Initialize a Fenwick Tree (BIT) of size `n` to all zeros. This BIT will be used to track which original indices have already been used.
*   Initialize an empty `StringBuilder` to build the result.
*   Iterate from `i = 0` to `n-1` to construct the result string character by character.
*   In each iteration `i`, iterate through the digits `d` from '0' to '9'.
    *   For each digit `d`, check if there are any available occurrences by looking at its corresponding queue.
    *   If so, get its first available original index, `p = positions.get(d).peek()`.
    *   Calculate the cost to move this digit to the current position. The cost is its relative position among the remaining digits, which is `p - (number of digits from original indices < p that have already been moved)`. 
    *   The number of moved digits before `p` can be found efficiently using the BIT: `moved_count = BIT.query(p-1)`.
    *   The cost is therefore `p - moved_count`.
    *   If `cost <= k`, this is the best digit to choose for the current position `i`. Append it to the result, update `k -= cost`, remove the index `p` from the queue, and mark index `p` as used in the BIT by calling `BIT.update(p, 1)`.
    *   Break the inner loop (over digits) and proceed to the next position `i+1`.
*   After the main loop, return the constructed string.

# Solutions
### Java

```java
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; }
}

```

### CPP

```cpp
class BinaryIndexedTree { public: int n ; vector < int > c ; BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += lowbit ( x ); } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= lowbit ( x ); } return s ; } int lowbit ( int x ) { return x & - x ; } }; class Solution { public: string minInteger ( string num , int k ) { vector < queue < int >> pos ( 10 ); int n = num . size (); for ( int i = 0 ; i < n ; ++ i ) pos [ num [ i ] - '0' ]. push ( i + 1 ); BinaryIndexedTree * tree = new BinaryIndexedTree ( n ); string ans = "" ; for ( int i = 1 ; i <= n ; ++ i ) { for ( int v = 0 ; v < 10 ; ++ v ) { auto & q = pos [ v ]; if ( ! q . empty ()) { int j = q . front (); int dist = tree -> query ( n ) - tree -> query ( j ) + j - i ; if ( dist <= k ) { k -= dist ; q . pop (); ans += ( v + '0' ); tree -> update ( j , 1 ); break ; } } } } return ans ; } };
```

### Python

```python
class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) @ staticmethod def lowbit ( x ): return x & - x def update ( self , x , delta ): while x <= self . n : self . c [ x ] += delta x += BinaryIndexedTree . lowbit ( x ) def query ( self , x ): s = 0 while x : s += self . c [ x ] x -= BinaryIndexedTree . lowbit ( x ) return s class Solution : def minInteger ( self , num : str , k : int ) -> str : pos = defaultdict ( deque ) for i , v in enumerate ( num , 1 ): pos [ int ( v )]. append ( i ) ans = [] n = len ( num ) tree = BinaryIndexedTree ( n ) for i in range ( 1 , n + 1 ): for v in range ( 10 ): q = pos [ v ] if q : j = q [ 0 ] dist = tree . query ( n ) - tree . query ( j ) + j - i if dist <= k : k -= dist q . popleft () ans . append ( str ( v )) tree . update ( j , 1 ) break return '' . join ( ans )
```