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);
}
}