Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution

Difficulty Level Hard
Frequently asked in Amazon FlipkartViews 152

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.

Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode Solution

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 k0 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

Translate »