You are given a string num, representing a large integer, and an integer k.

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


	For example, when num = "5489355142":

	
		The 1st smallest wonderful integer is "5489355214".
		The 2nd smallest wonderful integer is "5489355241".
		The 3rd smallest wonderful integer is "5489355412".
		The 4th smallest wonderful integer is "5489355421".
	
	


Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the kth smallest wonderful integer.

The tests are generated in such a way that kth&nbsp;smallest wonderful integer exists.

&nbsp;
Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -&gt; "5489355412"
- Swap index 8 with index 9: "5489355412" -&gt; "5489355421"


Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -&gt; "11121"
- Swap index 2 with index 3: "11121" -&gt; "11211"
- Swap index 1 with index 2: "11211" -&gt; "12111"
- Swap index 0 with index 1: "12111" -&gt; "21111"


Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -&gt; "00132"


&nbsp;
Constraints:


	2 &lt;= num.length &lt;= 1000
	1 &lt;= k &lt;= 1000
	num only consists of digits.


class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        num = list(num)
        orig = num.copy()
        
        for _ in range(k): 
            for i in reversed(range(len(num)-1)): 
                if num[i] < num[i+1]: 
                    ii = i+1 
                    while ii < len(num) and num[i] < num[ii]: ii += 1
                    num[i], num[ii-1] = num[ii-1], num[i]
                    lo, hi = i+1, len(num)-1
                    while lo < hi: 
                        num[lo], num[hi] = num[hi], num[lo]
                        lo += 1
                        hi -= 1
                    break 
        
        ans = 0
        for i in range(len(num)): 
            ii = i
            while orig[i] != num[i]: 
                ans += 1
                ii += 1
                num[i], num[ii] = num[ii], num[i]
        return ans 
class Solution {
    public int getMinSwaps(String num, int k) {
        int[] nums=new int[num.length()];
        int[] org=new int[num.length()];

        for(int i=0;i<num.length();i++){
            int e=Character.getNumericValue(num.charAt(i));
            nums[i]=e;
            org[i]=e;
        }

        while(k!=0){
        nextPermutation(nums);
         k--;
        }

        int ans=0;

        for(int i=0;i<nums.length;i++){

            if(nums[i]!=org[i]){
                int j=0;
                for(j=i+1;j<nums.length;j++)
                    if(org[j]==nums[i])
                        break;

                while(j>0 && j!=i){
                    swap(org,j,j-1);
                    ans++;
                    j--;
                }

            }

    }

      return ans;

    }

public void nextPermutation(int[] nums) {

        if(nums.length<=1)
            return;

        int j=nums.length-2;
       while(j>=0 && nums[j]>=nums[j+1])
           j--;

        if(j>=0){
        int k=nums.length-1;
        while(nums[j]>=nums[k])
            k--;

        swap(nums,j,k);

        }

        reverse(nums,j+1,nums.length-1);

    }

    public void swap(int[] nums,int j,int k){
        int temp=nums[j];
            nums[j]=nums[k];
            nums[k]=temp;
    }

    public void reverse(int[] nums,int i,int j){
        while(i<=j){
            swap(nums,i,j);
                i++;
                j--;
        }
    }
}
class Solution {
public:

    // GREEDY APPROACH
    // min steps to make strings equal

    int minSteps(string s1, string s2) {
        int size = s1.length();
        int i = 0, j = 0;
        int result = 0;

        while (i < size) {
            j = i;
            while (s1[j] != s2[i]) j++;

            while (i < j) {
                swap(s1[j], s1[j-1]);
                j--;
                result++;
            }
            i++;
        }
        return result;
    }

    int getMinSwaps(string num, int k) {
        string original = num;

        while(k--) {
            next_permutation(num.begin(), num.end());
        }

        return minSteps(original, num);
    }
};
var getMinSwaps = function(num, k) {
    
    const digits = [...num]
    const len = digits.length;
    
    // helper function to swap elements in digits in place
    const swap = (i, j) => [digits[i], digits[j]] = [digits[j], digits[i]]
    
    // helper function to reverse elements in digits from i to the end of digits
    const reverse = (i) => {
        for (let j = len - 1; i < j; ++i && --j) {
            swap(i, j);
        }
    }
    
    // helper to get the next smallest permutation for digits
    const nextPermutation = () => {
        // from right to left, find the first decreasing index
        // in digits and store it as i
        let i = len - 2;
        while (digits[i] >= digits[i + 1]) {
            i--;
        }
        
        // from right to left, find the first index in digits
        // that is greater than element at i
        let j = len - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }
        
        // swap the 2 elements at i and j
        swap(i, j);
        // reverse all elements after i because we know that
        // all elements after i are in ascending order
        // from right to left
        reverse(i + 1);
    }
    
    // find the next permutation k times
    for (let i = 0; i < k; i++) {
        nextPermutation();
    }

    // find out how many swaps it will take to get to the
    // kth permutation by finding out how many swaps
    // it takes to put digits back to its original state
    let numSwaps = 0;
    for (let i = 0; i < len; i++) {
        let j = i;
        // find the first element in digits to matches
        // num[i] and hold its place at j
        while (num[i] !== digits[j]) {
            j++;
        }
        
        // move the element at j to i while counting the
        // number of swaps
        while (i < j) {
            swap(j, j - 1);
            numSwaps++;
            j--;
        }
    }
    return numSwaps;
};
Minimum Adjacent Swaps to Reach the Kth Smallest Number