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

class Solution {
public:
    string minInteger(string a, int k) {
        int n=a.length();
        int req=(n+1)*n/2;       // upper limit for the number of swaps that is also less than 10^9 lowering our time complexity
        if(k>req){                    // that means we can try all swaps so returning minimum of all these by sorting 
            sort(a.begin(),a.end());   
            return a;
        }
        for(int i=0;i<n-1 && k>0;i++){
            //iterate in a window of size k 
            int pos=i;
            int j;
            for(j=i+1;j<n;j++){
                //out of window bound
                if(j-i>k){break;}
                //else if we actually wanna swap, we do
                if(a[j]<a[pos]){pos=j;}
            }
            //now assuming we swapped we have pos=j
            char temp;
            for(j=pos;j>i;j--){
                //we are swapping a[j] and a[j-1] finally we will have a[pos] swapped with a[i]
                temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
            //now update k value and do over if we wanna change the second most significant element to
            k-=pos-i;
        }
        return a;
    }
};
9100