Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1850.html

1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

Level

Medium

Description

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 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 4th smallest wonderful number is “5489355421”. To get this number:

  • Swap index 7 with index 8: “5489355142” -> “5489355412”
  • Swap index 8 with index 9: “5489355412” -> “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” -> “11121”
  • Swap index 2 with index 3: “11121” -> “11211”
  • Swap index 1 with index 2: “11211” -> “12111”
  • Swap index 0 with index 1: “12111” -> “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” -> “00132”

Constraints:

  • 2 <= num.length <= 1000
  • 1 <= k <= 1000
  • num only consists of digits.

Solution

Repeat k times to find the next permutation of num. Use original and swapped to represent the original string s and the k-th smallest number. Then use a greedy approach. Loop over original and swapped. If there exists an index i such that swapped[i] != original[i], then find the minimum index j such that swapped[i] == original[j] and move original[j] to original[i]. Calculate the number of swaps during the process. Finally, return the number of swaps.

  • class Solution {
    public int getMinSwaps(String num, int k) {
        int minSwaps = 0;
        char[] swapped = num.toCharArray();
        for (int i = 1; i <= k; i++)
            nextPermutation(swapped);
        char[] original = num.toCharArray();
        int length = original.length;
        for (int i = 0; i < length; i++) {
            if (swapped[i] != original[i]) {
                for (int j = i + 1; j < length; j++) {
                    if (swapped[i] == original[j]) {
                        for (int m = j - 1; m >= i; m--) {
                            original[m + 1] = original[m];
                            minSwaps++;
                        }
                        original[i] = swapped[i];
                        break;
                    }
                }
            }
        }
        return minSwaps;
    }

    public void nextPermutation(char[] array) {
        int i = array.length - 2;
        while (i >= 0 && array[i] >= array[i + 1])
            i--;
        if (i >= 0) {
            int j = array.length - 1;
            while (j >= 0 && array[i] >= array[j])
                j--;
            swap(array, i, j);
        }
        reverse(array, i + 1);
    }

    public void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public void reverse(char[] array, int start) {
        int left = start, right = array.length - 1;
        while (left < right) {
            swap(array, left, right);
            left++;
            right--;
        }
    }
}

  • // OJ: https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/
// Time: O(NK + N^2)
// Space: O(1)
class Solution {
public:
    int getMinSwaps(string s, int k) {
        auto start = s;
        for (int i = 0; i < k; ++i) {
            next_permutation(begin(s), end(s));
        }
        int ans = 0;
        for (int i = s.size() - 1; i >= 0; --i) {
            if (start[i] == s[i]) continue;
            int j = i - 1;
            while (j >= 0 && s[j] != start[i]) --j;
            ans += i - j;
            for (; j < i; ++j) s[j] = s[j + 1];
            s[i] = start[i];
        }
        return ans;
    }
};

  • # 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
# https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number

class Solution:
    def getMinSwaps(self, nums: str, k: int) -> int:
        n = len(nums)
        
        def nextPermutation(nums):
            i = n - 1
            while i > 0 and nums[i-1] >= nums[i]:
                i -= 1
            j = i
            while j < n and nums[i-1] < nums[j]:
                j += 1
            nums[i-1], nums[j-1] = nums[j-1], nums[i-1]
            nums[i:] = nums[i:][::-1]
            return nums
        
        swapped = list(nums)
        for _ in range(k):
            swapped = nextPermutation(swapped)
            
        nums = list(nums)
        res = 0
        for i in range(n):
            j = i
            
            while j < n and nums[i] != swapped[j]: j += 1

            while i < j:
                swapped[j], swapped[j - 1] = swapped[j-1], swapped[j]
                res += 1
                j -= 1

        return res
            
        


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

  • 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;
}

All Problems

All Solutions