Table of Contents
Problem Statement
Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution – 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.
Input: num = "4321", k = 4 Output: "1342" Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.
Explanation
Let’s figure out observations and then find out the data structure to implement them.
Observation 0: Well, we know that if we could get the smallest digit to the left, then we will be able to make a number smaller than we currently have. In that sense, a sorted number(Ascending) will already be the smallest.
So, let’s take pen and paper and try to find the smallest number we can form for this:
"4321", k = 4
So, let’s try to move from 1 to the leftmost position. From now on, I’ll call the current digit we are moving to the left as d:
"4321", k = 4
"4312", k = 3
"4132", k = 2
"1432", k = 1
Hmm, we can clearly observe:
Observation 1: when we move a digit to left, other digits are shifted to the right. i.e 432 got shifted to the right by 1.
But, wait. What if there was another digit to the right of d?
"43219", k = 4
"43129", k = 3
"41329", k = 2
"14329", k = 1
Well, the location of 9 didn’t change. Therefore, we can make some corrections to our above observation.
Corrected observation 1: Only digits to the left of d getting their position shifted.
Alright, what’s next?
But what if the k was really small and we couldn’t move from 1 to leftmost?
"43219", k = 2
"43129", k = 1
"41329", k = 0
We clearly didn’t reach the smallest number here. Smallest for k=2 would be 24319.
We can observe here, that we should choose the smallest d that is in the reach of k.
Observation 2: Choose first smallest d that is in reach of k.
If we combine all the observations, we can see that we will iterate from left to right and try to place digits 0 through 9.
Let’s work through a bigger example:
"9438957234785635408", k = 23
We will start from the left. Let’s try to place 0 here. 0 is within reach of k, 0 is 17 shifts away to right. So, we will get:
"0943895723478563548", k = 6
Observe that all the numbers got shifted to the right except the one to the right of d (8, here).
Now, let’s move to the next position:
Let’s try to place 0 here, again. But wait, we don’t have 0 left, so try 1, which is not there also. So let’s try 2, 2 is 8 distances away from this position. 8 > k, so we cannot choose 2. Let’s try 3, 3 is 2 distance away. 2 < k, therefore let’s choose 3.
"0394895723478563548", k = 4
and we can continue like this.
For observation 1, to calculate the correct number of shifts, we will need to also store how many elements before d already shifted. We will use a segment tree for this.
For observation 2, We will use a queue to choose the latest occurrence of each digit.
Code
Java Code for Minimum Possible Integer After at Most K Adjacent Swaps On Digits
class Solution {
public String minInteger(String num, int k) {
//pqs stores the location of each digit.
List<Queue<Integer>> pqs = new ArrayList<>();
for (int i = 0; i <= 9; ++i) {
pqs.add(new LinkedList<>());
}
for (int i = 0; i < num.length(); ++i) {
pqs.get(num.charAt(i) - '0').add(i);
}
String ans = "";
SegmentTree seg = new SegmentTree(num.length());
for (int i = 0; i < num.length(); ++i) {
// At each location, try to place 0....9
for (int digit = 0; digit <= 9; ++digit) {
// is there any occurrence of digit left?
if (pqs.get(digit).size() != 0) {
// yes, there is a occurrence of digit at pos
Integer pos = pqs.get(digit).peek();
// Since few numbers already shifted to left, this `pos` might be outdated.
// we try to find how many number already got shifted that were to the left of pos.
int shift = seg.getCountLessThan(pos);
// (pos - shift) is number of steps to make digit move from pos to i.
if (pos - shift <= k) {
k -= pos - shift;
seg.add(pos); // Add pos to our segment tree.
pqs.get(digit).remove();
ans += digit;
break;
}
}
}
}
return ans;
}
class SegmentTree {
int[] nodes;
int n;
public SegmentTree(int max) {
nodes = new int[4 * (max)];
n = max;
}
public void add(int num) {
addUtil(num, 0, n, 0);
}
private void addUtil(int num, int l, int r, int node) {
if (num < l || num > r) {
return;
}
if (l == r) {
nodes[node]++;
return;
}
int mid = (l + r) / 2;
addUtil(num, l, mid, 2 * node + 1);
addUtil(num, mid + 1, r, 2 * node + 2);
nodes[node] = nodes[2 * node + 1] + nodes[2 * node + 2];
}
// Essentialy it tells count of numbers < num.
public int getCountLessThan(int num) {
return getUtil(0, num, 0, n, 0);
}
private int getUtil(int ql, int qr, int l, int r, int node) {
if (qr < l || ql > r) return 0;
if (ql <= l && qr >= r) {
return nodes[node];
}
int mid = (l + r) / 2;
return getUtil(ql, qr, l, mid, 2 * node + 1) + getUtil(ql, qr, mid + 1, r, 2 * node + 2);
}
}
}Python Code for Minimum Possible Integer After at Most K Adjacent Swaps On Digits
class Solution:
def minInteger(self, num: str, k: int) -> str:
if k <= 0: return num
n = len(num)
if k >= n*(n-1)//2:
return "".join(sorted(list(num)))
# for each number, find the first index
for i in range(10):
ind = num.find(str(i))
if 0 <= ind <= k:
return str(num[ind]) + self.minInteger(num[0:ind] + num[ind+1:], k-ind)Complexity Analysis for Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution
Time Complexity
O(nLogn)
Space Complexity
O(N)
Reference: https://en.wikipedia.org/wiki/Fenwick_tree