Question - 9

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

class Solution {
    public String minInteger(String num, int k) {
        // list stores the location of each digit.
        List<Queue<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= 9; ++i)
            list.add(new LinkedList<>());
        for (int i = 0; i < num.length(); ++i)
            list.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 (list.get(digit).size() != 0) {
                    // yes, there is a occurrence of digit at pos
                    Integer pos = list.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;
                        // Add pos to our segment tree.
                        seg.add(pos);
                        list.get(digit).remove();
                        ans += digit;
                        break;
                    }
                }
            }
        }
        return ans;
    }

    class SegmentTree {
        int[] nodes;
        int n;

        // Segment tree only stores the indices of shifted elements
        public SegmentTree(int max) {
            nodes = new int[4 * (max)];
            n = max;
        }

        public void add(int num) {
            addUtil(num, 0, n, 1);
        }

        private void addUtil(int num, int start, int end, int index) {
            if (num < start || num > end)
                return;
            if (start == end) {
                nodes[index]++;
                return;
            }
            int mid = (start + end) / 2;
            addUtil(num, start, mid, 2 * index);
            addUtil(num, mid + 1, end, 2 * index + 1);
            nodes[index] = nodes[2 * index] + nodes[2 * index + 1];
        }

        // Essentialy it tells number of shifted numbers < num.
        public int getCountLessThan(int num) {
            return getUtil(0, num, 0, n, 1);
        }

        private int getUtil(int leftLimit, int rightLimit, int start, int end, int index) {
            // No overlap
            if (rightLimit < start || leftLimit > end)
                return 0;
            // Full overlap
            if (leftLimit <= start && rightLimit >= end)
                return nodes[index];
            // Partial overlap
            int mid = (start + end) / 2;
            return getUtil(leftLimit, rightLimit, start, mid, 2 * index)
                    + getUtil(leftLimit, rightLimit, mid + 1, end, 2 * index + 1);
        }
    }
}