1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution
In this guide, you will get 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution with the best time and space complexity. The solution to Minimum Possible Integer After at Most K Adjacent Swaps On Digits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Possible Integer After at Most K Adjacent Swaps On Digits
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.
1 <= num.length <= 3 * 104
num consists of only digits and does not contain leading zeros.
1 <= k <= 109
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution in C++
class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}
void add(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}
int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private:
vector<int> sums;
static inline int lowbit(int i) {
return i & -i;
}
};
class Solution {
public:
string minInteger(string num, int k) {
const int n = num.length();
string ans;
FenwickTree tree(n);
vector<bool> used(n);
vector<queue<int>> numToIndices(10);
for (int i = 0; i < n; ++i)
numToIndices[num[i] - '0'].push(i);
while (k > 0 && ans.length() < n)
for (int d = 0; d < 10; ++d) {
if (numToIndices[d].empty())
continue;
const int i = numToIndices[d].front();
const int cost = i - tree.get(i);
if (cost > k)
continue;
k -= cost;
ans += '0' + d;
used[i] = true;
tree.add(i + 1, 1);
numToIndices[d].pop();
break; // Scan from 0 -> 9 again.
}
for (int i = 0; i < n; ++i)
if (!used[i])
ans += num[i];
return ans;
}
}; /* code provided by PROGIEZ */
1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution in Java
N/A // code provided by PROGIEZ
1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution in Python
