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

String Binary Indexed Tree Segment 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 * 10⁴
num consists of only digits and does not contain leading zeros.
1 <= k <= 10⁹

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:

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.
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.
The cost of this operation is best_j - i swaps. We subtract this cost from k.
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".

1class Solution {2    public String minInteger(String num, int k) {3        StringBuilder sb = new StringBuilder(num);4        int n = num.length();5        for (int i = 0; i < n && k > 0; i++) {6            int bestIdx = i;7            // Find the smallest digit within reach8            for (int j = i + 1; j < n && j - i <= k; j++) {9                if (sb.charAt(j) < sb.charAt(bestIdx)) {10                    bestIdx = j;11                }12            }13            14            if (bestIdx != i) {15                char c = sb.charAt(bestIdx);16                sb.deleteCharAt(bestIdx);17                sb.insert(i, c);18                k -= (bestIdx - i);19            }20        }21        return sb.toString();22    }23}

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.

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.

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.

Walkthrough

The algorithm is as follows:

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'.
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).
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.

1class FenwickTree {2    private int[] bit;3    private int n;4 5    public FenwickTree(int size) {6        this.n = size;7        this.bit = new int[n + 1];8    }9 10    // Update value at 0-based index11    public void update(int index, int delta) {12        index++; // Convert to 1-based index13        while (index <= n) {14            bit[index] += delta;15            index += index & -index;16        }17    }18 19    // Query sum up to 0-based index20    public int query(int index) {21        if (index < 0) return 0;22        index++; // Convert to 1-based index23        int sum = 0;24        while (index > 0) {25            sum += bit[index];26            index -= index & -index;27        }28        return sum;29    }30}31 32class Solution {33    public String minInteger(String num, int k) {34        int n = num.length();35        List<Queue<Integer>> positions = new ArrayList<>();36        for (int i = 0; i < 10; i++) {37            positions.add(new LinkedList<>());38        }39        for (int i = 0; i < n; i++) {40            positions.get(num.charAt(i) - '0').add(i);41        }42 43        StringBuilder result = new StringBuilder();44        FenwickTree ft = new FenwickTree(n);45 46        for (int i = 0; i < n; i++) {47            for (int d = 0; d < 10; d++) {48                if (!positions.get(d).isEmpty()) {49                    int originalIndex = positions.get(d).peek();50                    int movedCount = ft.query(originalIndex - 1);51                    int cost = originalIndex - movedCount;52 53                    if (cost <= k) {54                        k -= cost;55                        result.append((char)('0' + d));56                        positions.get(d).poll();57                        ft.update(originalIndex, 1);58                        break; 59                    }60                }61            }62        }63        return result.toString();64    }65}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  String minInteger(String num, int k) {4    Queue<Integer>[] pos = new Queue[10];5    for (int i = 0; i < 10; ++i) {6      pos[i] = new ArrayDeque<>();7    }8    int n = num.length();9    for (int i = 0; i < n; ++i) {10      pos[num.charAt(i) - '0'].offer(i + 1);11    }12    StringBuilder ans = new StringBuilder();13    BinaryIndexedTree tree = new BinaryIndexedTree(n);14    for (int i = 1; i <= n; ++i) {15      for (int v = 0; v < 10; ++v) {16        if (!pos[v].isEmpty()) {17          Queue<Integer> q = pos[v];18          int j = q.peek();19          int dist = tree.query(n) - tree.query(j) + j - i;20          if (dist <= k) {21            k -= dist;22            q.poll();23            ans.append(v);24            tree.update(j, 1);25            break;26          }27        }28      }29    }30    return ans.toString();31  }32} class BinaryIndexedTree {33private34  int n;35private36  int[] c;37public38  BinaryIndexedTree(int n) {39    this.n = n;40    c = new int[n + 1];41  }42public43  void update(int x, int delta) {44    while (x <= n) {45      c[x] += delta;46      x += lowbit(x);47    }48  }49public50  int query(int x) {51    int s = 0;52    while (x > 0) {53      s += c[x];54      x -= lowbit(x);55    }56    return s;57  }58public59  static int lowbit(int x) { return x & -x; }60}

1class 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 ; } };

1class 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 )

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 problem