<p>You are given a string <code>num</code> representing <strong>the digits</strong> of a very large integer and an integer <code>k</code>. You are allowed to swap any two adjacent digits of the integer <strong>at most</strong> <code>k</code> times.</p>

<p>Return <em>the minimum integer you can obtain also as a string</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/17/q4_1.jpg" style="width: 500px; height: 40px;" />
<pre>
<strong>Input:</strong> num = &quot;4321&quot;, k = 4
<strong>Output:</strong> &quot;1342&quot;
<strong>Explanation:</strong> The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;100&quot;, k = 1
<strong>Output:</strong> &quot;010&quot;
<strong>Explanation:</strong> It&#39;s ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;36789&quot;, k = 1000
<strong>Output:</strong> &quot;36789&quot;
<strong>Explanation:</strong> We can keep the number without any swaps.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>num</code> consists of only <strong>digits</strong> and does not contain <strong>leading zeros</strong>.</li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

/*
  thought:
    1. the basic idea is to change the leftmost non-min to the possible min
       said the leftmost non-min is x and there is y_i1 > y_i2 > x, i1 < i2
       and y_i1, y_i2 are both min in the x and its post nums
       it is like num=...x...y_i1...yi2 then let's focus on x, and 2 y
       said the ... before x is pre_i and ... after x are post_j
       then, pre_i <= y_i2 < y_i1 < x <= post_j
       (pre_i and post_j are group of nums, where pre_i is non-decreasing for all i)
       
       if k is enough for y_i2, said need k_i2, just swap y_i2 to the position of x
          so num = ...y_i2 x ...y_i1.... and it will be the min with k_i2 swaps
          (ie. moving x.. pre_yi2 right 1 step)
          then still check x and y_i1 (but now x index++)
       if k is not enough for y_i2, but enough for y_i1, do it for y_i1
          then move to the next num after y_i2 (or the position of original x)
       if k is not enough for both, let's select the num next to x
          then find its y_i to do the decision, till k exhausted
       
       
  1. greedy + BIT:
     a) prepare a lut[i] = stack, where i is for digits 0..9 and stack is the related
        index increasing from top to bottomm
        and a visisted array size as num
        a BIT to record how many nums in visited array are marked true
              (how many nums are aleady swapped forward)
              to shift i to its correct position
        and a res
     b)  i = 0
         while i < n and k > 0
          if visited[i] == true
             i++
          else
             find the shift from BIT
             then i_adj = i + shift // since there are some nums after moved forward
                                    // i need to adjusted for them
             
             // find the min j which can swap to the position of i_adj
             for j = 0..nums[i] - 1
                while st[j].top is visited, pop it // these nums are used in res
                if st is empty, continue
                find j_adj = st[j].top + shift from BIT // st[j].top need shift too
                                                        // => j_adj is not j shift
                                                        // but a short for j top shift
                // if a valid nums found, move it forward (put into res)
                // then no more need to check the rest j so beak
                if j_adj - i_adj <= k
                   k -= j_adj - i_adj
                   visited[st[j].top] = true
                   update BIT by st[j].top
                   res += j
                   pop st[j]
                   break
              
              // no any nums found for i, so put nums[i] into res
              if j == nums[i]
                 visited[i] = true
                 res += nums[i]
                 update BIT by i // necessary ?
                 i++
                 
        //out of while i < n and k > 0
        for j=i..n-1
           put all visite[i] false to res
           

*/
class Solution {
private:
    void updateBIT(int i) {
        i = n - i;
        while (i <= n) {
            ++BIT[i];
            i += i&(-i);
        }
    }
    
    int getBIT(int i) {
        i = n - i;
        int res = 0;
        while (i > 0) {
            res += BIT[i];
            i &= i - 1;
        }
        
        return res;
    }
    
public:
    string minInteger(string num, int k) {
        n = num.length();
        BIT.resize(n + 1, 0);
        
        vector<vector<int>> st(10);
        
        for (int i = n - 1; i >= 0; --i) {
            int digit = num[i] - '0';
            st[digit].push_back(i);
        }
        
        vector<bool> visited(n, false);
        
        string res;
        int i = 0;
        while (i < n && k) {
            if (visited[i])
                ++i;
            else {
                int i_adj = i + getBIT(i); // i must be false so no need to check i + 1
                                           // but i + 1 is OK even i == n - 1
                
                int digit = 0, max_digit = num[i] - '0';
                for (; digit < max_digit; ++digit) {
                    while (st[digit].size() && visited[st[digit].back()])
                        st[digit].pop_back();
                    
                    if (st[digit].empty())
                        continue;
                    
                    int j = st[digit].back();
                    int j_adj = j + getBIT(j);

                    if (j_adj - i_adj <= k) {

                        st[digit].pop_back();
                        k -= j_adj - i_adj;
                        visited[j] = true;
                        updateBIT(j);
                        res += (digit + '0');

                        break;
                    }

                }
                
                if (digit == max_digit) {
                    res += num[i];
                    visited[i] = true;
                    //updateBIT(i); // since BIT only care post i, this is not required
                    ++i;
                }

            }
        }
        
        for (; i < n; ++i)
            if (!visited[i])
                res += num[i];
        
        return res;
    }

private:
    int n;
    vector<int> BIT;
};



12500