<p>You are given a string <code>num</code>, representing a large integer, and an integer <code>k</code>.</p>

<p>We call some integer <strong>wonderful</strong> if it is a <strong>permutation</strong> of the digits in <code>num</code> and is <strong>greater in value</strong> than <code>num</code>. There can be many wonderful integers. However, we only care about the <strong>smallest-valued</strong> ones.</p>

<ul>
	<li>For example, when <code>num = &quot;5489355142&quot;</code>:

	<ul>
		<li>The 1<sup>st</sup> smallest wonderful integer is <code>&quot;5489355214&quot;</code>.</li>
		<li>The 2<sup>nd</sup> smallest wonderful integer is <code>&quot;5489355241&quot;</code>.</li>
		<li>The 3<sup>rd</sup> smallest wonderful integer is <code>&quot;5489355412&quot;</code>.</li>
		<li>The 4<sup>th</sup> smallest wonderful integer is <code>&quot;5489355421&quot;</code>.</li>
	</ul>
	</li>
</ul>

<p>Return <em>the <strong>minimum number of adjacent digit swaps</strong> that needs to be applied to </em><code>num</code><em> to reach the </em><code>k<sup>th</sup></code><em><strong> smallest wonderful</strong> integer</em>.</p>

<p>The tests are generated in such a way that <code>k<sup>th</sup></code>&nbsp;smallest wonderful integer exists.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;5489355142&quot;, k = 4
<strong>Output:</strong> 2
<strong>Explanation:</strong> The 4<sup>th</sup> smallest wonderful number is &quot;5489355421&quot;. To get this number:
- Swap index 7 with index 8: &quot;5489355<u>14</u>2&quot; -&gt; &quot;5489355<u>41</u>2&quot;
- Swap index 8 with index 9: &quot;54893554<u>12</u>&quot; -&gt; &quot;54893554<u>21</u>&quot;
</pre>

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

<pre>
<strong>Input:</strong> num = &quot;11112&quot;, k = 4
<strong>Output:</strong> 4
<strong>Explanation:</strong> The 4<sup>th</sup> smallest wonderful number is &quot;21111&quot;. To get this number:
- Swap index 3 with index 4: &quot;111<u>12</u>&quot; -&gt; &quot;111<u>21</u>&quot;
- Swap index 2 with index 3: &quot;11<u>12</u>1&quot; -&gt; &quot;11<u>21</u>1&quot;
- Swap index 1 with index 2: &quot;1<u>12</u>11&quot; -&gt; &quot;1<u>21</u>11&quot;
- Swap index 0 with index 1: &quot;<u>12</u>111&quot; -&gt; &quot;<u>21</u>111&quot;
</pre>

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

<pre>
<strong>Input:</strong> num = &quot;00123&quot;, k = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> The 1<sup>st</sup> smallest wonderful number is &quot;00132&quot;. To get this number:
- Swap index 3 with index 4: &quot;001<u>23</u>&quot; -&gt; &quot;001<u>32</u>&quot;
</pre>

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

<ul>
	<li><code>2 &lt;= num.length &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>num</code> only consists of digits.</li>
</ul>

class Solution:
    def get_invcnt(self,a):
        def mergeHelper(l,mid,r,a):
            temp = [0]*(r-l+1)
            k = 0
            i,j = l,mid+1
            invcnt = 0
            while i<=mid and j<=r:
                if a[i]<=a[j]:
                    temp[k] = a[i]
                    i+=1
                else:
                    temp[k] = a[j]
                    invcnt += (mid+1-i)
                    j+=1
                k+=1
            while i<=mid:
                temp[k] = a[i]
                i+=1;k+=1
            while j<=mid:
                temp[k] = a[j]
                j+=1;k+=1
            for i in range(k):
                a[l+i] = temp[i]
            return invcnt
        def merge(l,r,a):
            ans = 0
            if l<r:
                mid = (l+r)//2
                left = merge(l,mid,a)
                right = merge(mid+1,r,a)
                merging = mergeHelper(l,mid,r,a)
                ans = left+right+merging
            return ans
        inv_count = merge(0,len(a)-1,a)
        return inv_count
    def getNextPerm(self,a):
        n = len(a)
        j = n-1
        while j-1>=0 and a[j-1]>=a[j]:
            j-=1
        if j==0:
            a.reverse()
            return
        i = j-1
        k = n-1
        while a[i]>=a[k]:
            k-=1
        a[i],a[k] = a[k],a[i]
        ele = n-j
        for l in range(ele//2):
            a[j+l],a[n-1-l] = a[n-1-l],a[j+l]
        return
    def getMinSwaps(self, num: str, k: int) -> int:
        n = len(num)
        a = list(num)
        orig = a.copy()
        for i in range(k):
            self.getNextPerm(a)
        ind = {}
        for i in range(n-1,-1,-1):
            val = orig[i]
            if val not in ind:
                ind[val] = []
            ind[val].append(i)
        b = [ind[a[i]].pop() for i in range(n)]
        inv_cnt = self.get_invcnt(b)
        return inv_cnt
        
979