Minimum Adjacent Swaps to Reach the Kth Smallest Number

// Accepted solution for LeetCode #1850: Minimum Adjacent Swaps to Reach the Kth Smallest Number
class Solution {
    public int getMinSwaps(String num, int k) {
        char[] s = num.toCharArray();
        for (int i = 0; i < k; ++i) {
            nextPermutation(s);
        }
        List<Integer>[] d = new List[10];
        Arrays.setAll(d, i -> new ArrayList<>());
        int n = s.length;
        for (int i = 0; i < n; ++i) {
            d[num.charAt(i) - '0'].add(i);
        }
        int[] idx = new int[10];
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = d[s[i] - '0'].get(idx[s[i] - '0']++);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[j] > arr[i]) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private boolean nextPermutation(char[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i < 0) {
            return false;
        }
        int j = n - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            --j;
        }
        swap(nums, i++, j);
        for (j = n - 1; i < j; ++i, --j) {
            swap(nums, i, j);
        }
        return true;
    }

    private void swap(char[] nums, int i, int j) {
        char t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

// Accepted solution for LeetCode #1850: Minimum Adjacent Swaps to Reach the Kth Smallest Number
func getMinSwaps(num string, k int) (ans int) {
	s := []byte(num)
	for ; k > 0; k-- {
		nextPermutation(s)
	}
	d := [10][]int{}
	for i, c := range num {
		j := int(c - '0')
		d[j] = append(d[j], i)
	}
	idx := [10]int{}
	n := len(s)
	arr := make([]int, n)
	for i, c := range s {
		j := int(c - '0')
		arr[i] = d[j][idx[j]]
		idx[j]++
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if arr[j] > arr[i] {
				ans++
			}
		}
	}
	return
}

func nextPermutation(nums []byte) bool {
	n := len(nums)
	i := n - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i < 0 {
		return false
	}
	j := n - 1
	for j >= 0 && nums[j] <= nums[i] {
		j--
	}
	nums[i], nums[j] = nums[j], nums[i]
	for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
	return true
}

# Accepted solution for LeetCode #1850: Minimum Adjacent Swaps to Reach the Kth Smallest Number
class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        def next_permutation(nums: List[str]) -> bool:
            n = len(nums)
            i = n - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1
            if i < 0:
                return False
            j = n - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
            nums[i + 1 : n] = nums[i + 1 : n][::-1]
            return True

        s = list(num)
        for _ in range(k):
            next_permutation(s)
        d = [[] for _ in range(10)]
        idx = [0] * 10
        n = len(s)
        for i, c in enumerate(num):
            j = ord(c) - ord("0")
            d[j].append(i)
        arr = [0] * n
        for i, c in enumerate(s):
            j = ord(c) - ord("0")
            arr[i] = d[j][idx[j]]
            idx[j] += 1
        return sum(arr[j] > arr[i] for i in range(n) for j in range(i))

// Accepted solution for LeetCode #1850: Minimum Adjacent Swaps to Reach the Kth Smallest Number
/**
 * [1850] Minimum Adjacent Swaps to Reach the Kth Smallest Number
 *
 * 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 1^st smallest wonderful integer is "5489355214".
 * 		The 2^nd smallest wonderful integer is "5489355241".
 * 		The 3^rd smallest wonderful integer is "5489355412".
 * 		The 4^th smallest wonderful integer is "5489355421".
 *
 *
 *
 * Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.
 * The tests are generated in such a way that k^th smallest wonderful integer exists.
 *  
 * Example 1:
 *
 * Input: num = "5489355142", k = 4
 * Output: 2
 * Explanation: The 4^th smallest wonderful number is "5489355421". To get this number:
 * - Swap index 7 with index 8: "5489355<u>14</u>2" -> "5489355<u>41</u>2"
 * - Swap index 8 with index 9: "54893554<u>12</u>" -> "54893554<u>21</u>"
 *
 * Example 2:
 *
 * Input: num = "11112", k = 4
 * Output: 4
 * Explanation: The 4^th smallest wonderful number is "21111". To get this number:
 * - Swap index 3 with index 4: "111<u>12</u>" -> "111<u>21</u>"
 * - Swap index 2 with index 3: "11<u>12</u>1" -> "11<u>21</u>1"
 * - Swap index 1 with index 2: "1<u>12</u>11" -> "1<u>21</u>11"
 * - Swap index 0 with index 1: "<u>12</u>111" -> "<u>21</u>111"
 *
 * Example 3:
 *
 * Input: num = "00123", k = 1
 * Output: 1
 * Explanation: The 1^st smallest wonderful number is "00132". To get this number:
 * - Swap index 3 with index 4: "001<u>23</u>" -> "001<u>32</u>"
 *
 *  
 * Constraints:
 *
 * 	2 <= num.length <= 1000
 * 	1 <= k <= 1000
 * 	num only consists of digits.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/
// discuss: https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn get_min_swaps(num: String, k: i32) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_1850_example_1() {
        let num = "5489355142".to_string();
        let k = 4;

        let result = 2;

        assert_eq!(Solution::get_min_swaps(num, k), result);
    }

    #[test]
    #[ignore]
    fn test_1850_example_2() {
        let num = "11112".to_string();
        let k = 4;

        let result = 4;

        assert_eq!(Solution::get_min_swaps(num, k), result);
    }

    #[test]
    #[ignore]
    fn test_1850_example_3() {
        let num = "00123".to_string();
        let k = 1;

        let result = 1;

        assert_eq!(Solution::get_min_swaps(num, k), result);
    }
}

// Accepted solution for LeetCode #1850: Minimum Adjacent Swaps to Reach the Kth Smallest Number
function getMinSwaps(num: string, k: number): number {
    const n = num.length;
    const s = num.split('');
    for (let i = 0; i < k; ++i) {
        nextPermutation(s);
    }
    const d: number[][] = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < n; ++i) {
        d[+num[i]].push(i);
    }
    const idx: number[] = Array(10).fill(0);
    const arr: number[] = [];
    for (let i = 0; i < n; ++i) {
        arr.push(d[+s[i]][idx[+s[i]]++]);
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (arr[j] > arr[i]) {
                ans++;
            }
        }
    }
    return ans;
}

function nextPermutation(nums: string[]): boolean {
    const n = nums.length;
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i < 0) {
        return false;
    }
    let j = n - 1;
    while (j >= 0 && nums[i] >= nums[j]) {
        j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
    for (i = i + 1, j = n - 1; i < j; ++i, --j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return true;
}