Formatted question description: https://leetcode.ca/all/1505.html

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

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.

Example 4:

Input: num = "22", k = 22
Output: "22"

Example 5:

Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

 

Constraints:

• 1 <= num.length <= 30000
• num contains digits only and doesn't have leading zeros.
• 1 <= k <= 10^9

Related Topics:
Greedy

Solution 1. Segment Tree

// OJ: https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/

// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/discuss/720548/O(n-logn)-or-Java-or-Heavily-Commented-or-Segment-Tree-or-Detailed-Explanation
class SegmentTree {
    vector<int> A;
    int N;
    void addUntil(int num, int L, int R, int node) {
        if (num < L || num > R) return;
        if (L == R) {
            A[node]++;
            return;
        }
        int M = (L + R) / 2;
        addUntil(num, L, M, 2 * node + 1);
        addUntil(num, M + 1, R, 2 * node + 2);
        A[node] = A[2 * node + 1] + A[2 * node + 2];
    }
    int getUntil(int qL, int qR, int L, int R, int node) {
        if (qR < L || qL > R) return 0;
        if (qL <= L && qR >= R) return A[node];
        int M = (L + R) / 2;
        return getUntil(qL, qR, L, M, 2 * node + 1) + getUntil(qL, qR, M + 1, R, 2 * node + 2);
    }
public:
    SegmentTree(int n) : A(4 * n), N(n) {}
    void add (int num) { addUntil(num, 0, N, 0); }
    int countLessThan(int num) { return getUntil(0, num, 0, N, 0); }
};
class Solution {
public:
    string minInteger(string A, int k) {
        queue<int> q[10];
        int N = A.size();
        for (int i = 0; i < N; ++i) q[A[i] - '0'].push(i);
        string ans;
        SegmentTree tree(N);
        for (int i = 0; i < N; ++i) {
            for (int d = 0; d <= 9; ++d) {
                if (q[d].empty()) continue;
                int j = q[d].front(), shift = tree.countLessThan(j);
                if (j - shift > k) continue;
                k -= j - shift;
                tree.add(j);
                q[d].pop();
                ans += '0' + d;
                break;
            }
        }
        return ans;
    }
};

Java

class Solution {
    public String minInteger(String num, int k) {
        char[] array = num.toCharArray();
        int length = array.length;
        int index = 0;
        while (k > 0 && index < length) {
            int minDigit = array[index] - '0', minIndex = index;
            int upperBound = Math.min(length - 1, index + k);
            for (int i = index + 1; i <= upperBound; i++) {
                int digit = array[i] - '0';
                if (digit < minDigit) {
                    minDigit = digit;
                    minIndex = i;
                }
            }
            k -= (minIndex - index);
            char c = array[minIndex];
            for (int i = minIndex - 1; i >= index; i--)
                array[i + 1] = array[i];
            array[index] = c;
            index++;
        }
        return new String(array);
    }
}

All Problems

All Solutions