# 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
# Medium

# 35

# 11

# Add to List

# Share
# 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 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.

# This solution works:

class Solution:
    '''
    54321->none
    
    454321->512344
    
    354321->412335
    453321
    '''
    def getMinSwaps(self, num: str, k: int) -> int:
        digits = list(num)
        for _ in range(k):
            idx1 = len(digits) - 2
            while digits[idx1] >= digits[idx1+1]:
                idx1 -= 1
            idx2 = idx1 + 1
            while idx2 + 1 < len(digits) and digits[idx2+1] > digits[idx1]:
                idx2 += 1
            digits[idx1], digits[idx2] = digits[idx2], digits[idx1]
            left, right = idx1 + 1, len(digits) - 1
            while left < right:
                digits[left], digits[right] = digits[right], digits[left]
                left += 1
                right -= 1
        
        ans = 0
        for i, c in enumerate(num):
            if digits[i] == c:
                continue
            j = i + 1
            while digits[j] != c:
                j += 1
            ans += j - i
            for idx in range(j, i-1, -1):
                digits[idx] = digits[idx - 1]
        return ans
1f589df19ac79258876631a2ad82378643378794
<mask token>

class Solution:
    <mask token>
    <mask token>

class Solution:
    <mask token>

    def getMinSwaps(self, num: str, k: int) ->int:
        digits = list(num)
        for _ in range(k):
            idx1 = len(digits) - 2
            while digits[idx1] >= digits[idx1 + 1]:
                idx1 -= 1
            idx2 = idx1 + 1
            while idx2 + 1 < len(digits) and digits[idx2 + 1] > digits[idx1]:
                idx2 += 1
            digits[idx1], digits[idx2] = digits[idx2], digits[idx1]
            left, right = idx1 + 1, len(digits) - 1
            while left < right:
                digits[left], digits[right] = digits[right], digits[left]
                left += 1
                right -= 1
        ans = 0
        for i, c in enumerate(num):
            if digits[i] == c:
                continue
            j = i + 1
            while digits[j] != c:
                j += 1
            ans += j - i
            for idx in range(j, i - 1, -1):
                digits[idx] = digits[idx - 1]
        return ans

class Solution:
    """
    54321->none
    
    454321->512344
    
    354321->412335
    453321
    """

    def getMinSwaps(self, num: str, k: int) ->int:
        digits = list(num)
        for _ in range(k):
            idx1 = len(digits) - 2
            while digits[idx1] >= digits[idx1 + 1]:
                idx1 -= 1
            idx2 = idx1 + 1
            while idx2 + 1 < len(digits) and digits[idx2 + 1] > digits[idx1]:
                idx2 += 1
            digits[idx1], digits[idx2] = digits[idx2], digits[idx1]
            left, right = idx1 + 1, len(digits) - 1
            while left < right:
                digits[left], digits[right] = digits[right], digits[left]
                left += 1
                right -= 1
        ans = 0
        for i, c in enumerate(num):
            if digits[i] == c:
                continue
            j = i + 1
            while digits[j] != c:
                j += 1
            ans += j - i
            for idx in range(j, i - 1, -1):
                digits[idx] = digits[idx - 1]
        return ans

# 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
# Medium

# 35

# 11

# Add to List

# Share
# 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 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.

# This solution works:

class Solution:
    '''
    54321->none
    
    454321->512344
    
    354321->412335
    453321
    '''
    def getMinSwaps(self, num: str, k: int) -> int:
        digits = list(num)
        for _ in range(k):
            idx1 = len(digits) - 2
            while digits[idx1] >= digits[idx1+1]:
                idx1 -= 1
            idx2 = idx1 + 1
            while idx2 + 1 < len(digits) and digits[idx2+1] > digits[idx1]:
                idx2 += 1
            digits[idx1], digits[idx2] = digits[idx2], digits[idx1]
            left, right = idx1 + 1, len(digits) - 1
            while left < right:
                digits[left], digits[right] = digits[right], digits[left]
                left += 1
                right -= 1
        
        ans = 0
        for i, c in enumerate(num):
            if digits[i] == c:
                continue
            j = i + 1
            while digits[j] != c:
                j += 1
            ans += j - i
            for idx in range(j, i-1, -1):
                digits[idx] = digits[idx - 1]
        return ans