Minimum adjacent swaps required to get Kth smallest number greater than given number - Coding

Given numeric string S of size N and a positive integer K, the task is to find the minimum number of adjacent swaps required in S to obtain the K^th smallest numeric string greater than the given string.

Examples:

Input: S = “11112”, K = 4
Output: 4
Explanation:
The K^th(= 4^th) smallest numeric string which is greater than the given string is “21111”. The sequence of adjacent swap to reach the string “21111” is “11112” -> “11121” -> “11211″ -> “12111″ -> “21111″.
Therefore, the minimum number of adjacent swaps required is 4.

Input: S = “12345”, K = 1
Output: 1

Approach: The given problem can be solved by using the Greedy Approach. Follow the steps below to solve the problem:

Store the copy of the current numeric string in a variable, say res.
Create a variable, say totalSwaps that stores the minimum swaps required.
Since K-th largest number is required, this statement is equal to finding K-th permutation starting from the current string.
Find the K-th permutation using the function next_permutation().
Iterate over the range [0, N) using the variable i and perform the following tasks:
- If res[i] is not equal to str[i] then initialize the variable start as i+1 and traverse over a while loop till res[i] is not equal to str[start] and increase the value of i by 1.
- Iterate a loop till i is not equal to start and swap the values str[start] and str[start – 1] and decrease the value of start by 1 and increase the value of totalSwaps by 1.
After performing the above steps, print the value of totalSwaps as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of swaps required to make the Kth
// smallest string greater than str
void minSwapsKthLargest(string str, int k)
{
    // Store the copy of the string
    string res = str;
 
    // Find the K-th permutation of
    // the given numeric string
    for (int i = 0; i < k; i++) {
        next_permutation(
            str.begin(), str.end());
      cout<<"str = "<<str<<endl;
    }
 
    // Stores the count of swaps required
    int swap_count = 0;
 
    // Traverse the string and find the
    // swaps required greedily
    for (int i = 0; i < res.length(); i++) {
 
        // If both characters do not match
        if (res[i] != str[i]) {
            int start = i + 1;
 
            // Search from i+1 index
            while (res[i] != str[start]) {
 
                // Find the index to swap
                start++;
            }
            while (i != start) {
                swap(str[start], str[start - 1]);
 
                // Swap until the characters
                // are at same index
                start--;
                swap_count++;
            }
        }
    }
 
    // Print the minimum number of counts
    cout << swap_count;
}
 
// Driver Code
int main()
{
    string S = "11112";
    int K = 4;
    minSwapsKthLargest(S, K);
 
    return 0;
}

Java

// Java program for the above approach
 
import java.util.*;
 
class GFG {
    static char[] next_permutation(char[] array) {
        int i = array.length - 1;
        while (i > 0 && array[i - 1] >= array[i]) {
            i--;
        }
 
        int j = array.length - 1;
 
        while (array[j] <= array[i - 1]) {
            j--;
        }
 
        char temp = array[i - 1];
        array[i - 1] = array[j];
        array[j] = temp;
 
        j = array.length - 1;
 
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
 
        return array;
    }
 
    // Function to find the minimum number
    // of swaps required to make the Kth
    // smallest String greater than str
    static void minSwapsKthLargest(String str, int k) 
    {
       
        // Store the copy of the String
        char[] res = str.toCharArray();
        char[] s = str.toCharArray();
       
        // Find the K-th permutation of
        // the given numeric String
        for (int i = 0; i < k; i++) {
            s = next_permutation(s);
        }
 
        // Stores the count of swaps required
        int swap_count = 0;
 
        // Traverse the String and find the
        // swaps required greedily
        for (int i = 0; i < res.length; i++) {
 
            // If both characters do not match
            if (res[i] != s[i]) {
                int start = i + 1;
 
                // Search from i+1 index
                while (res[i] != s[start]) {
 
                    // Find the index to swap
                    start++;
                }
                while (i != start) {
                    char t = s[start];
                    s[start] = s[start - 1];
                    s[start - 1] = t;
                    // Swap until the characters
                    // are at same index
                    start--;
                    swap_count++;
                }
            }
        }
 
        // Print the minimum number of counts
        System.out.print(swap_count);
    }
 
    // Driver Code
    public static void main(String[] args) {
        String S = "11112";
        int K = 4;
        minSwapsKthLargest(S, K);
 
    }
}
 
// This code is contributed by Rajput-Ji 

Python3

# Python Program to implement
# the above approach
def next_permutation(array):
 
    i = len(array) - 1
    while (i > 0 and ord(array[i - 1]) >= ord(array[i])):
        i -= 1
 
    if (i <= 0):
        return False
 
    j = len(array) - 1
 
    while (ord(array[j]) <= ord(array[i - 1])):
        j -= 1
 
    array[j],array[i - 1] = array[i - 1],array[j]
 
    j = len(array) - 1
 
    while (i < j):
        array[i],array[j] = array[j],array[i]
        i += 1
        j -= 1
 
    return array
 
# Function to find the minimum number
# of swaps required to make the Kth
# smallest string greater than str
def minSwapsKthLargest(Str, k):
 
    # Store the copy of the string
    res = list(Str)
    Str = list(Str)
 
    # Find the K-th permutation of
    # the given numeric string
    for i in range(k):
        next_permutation(Str)
 
    # Stores the count of swaps required
    swap_count = 0
 
    # Traverse the string and find the
    # swaps required greedily
    for i in range(len(res)):
 
        # If both characters do not match
        if (res[i] != Str[i]):
            start = i + 1
 
            # Search from i+1 index
            while (res[i] != Str[start]):
 
                # Find the index to swap
                start += 1
 
            while (i != start):
                Str[start],Str[start-1] = Str[start-1],Str[start] 
 
                # Swap until the characters
                # are at same index
                start -= 1
                swap_count += 1
 
    # Print the minimum number of counts
    print(swap_count)
 
# Driver Code
S = "11112"
K = 4
minSwapsKthLargest(S, K)
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
class GFG {
 
    static char[] next_permutation(char[] array)
    {
        int i = array.Length - 1;
        while (i > 0 && array[i - 1] >= array[i]) {
            i--;
        }
 
        int j = array.Length - 1;
 
        while (array[j] <= array[i - 1]) {
            j--;
        }
 
        char temp = array[i - 1];
        array[i - 1] = array[j];
        array[j] = temp;
 
        j = array.Length - 1;
 
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
 
        return array;
    }
 
    // Function to find the minimum number
    // of swaps required to make the Kth
    // smallest string greater than str
    static void minSwapsKthLargest(string str, int k)
    {
        // Store the copy of the string
        string res = str;
        char[] str1 = str.ToCharArray();
 
        // Find the K-th permutation of
        // the given numeric string
        for (int i = 0; i < k; i++) {
            next_permutation(str1);
        }
 
        // Stores the count of swaps required
        int swap_count = 0;
 
        // Traverse the string and find the
        // swaps required greedily
        for (int i = 0; i < res.Length; i++) {
 
            // If both characters do not match
            if (res[i] != str1[i]) {
                int start = i + 1;
 
                // Search from i+1 index
                while (res[i] != str1[start]) {
 
                    // Find the index to swap
                    start++;
                }
                while (i != start) {
                    char temp = str1[start];
                    str1[start] = str1[start - 1];
                    str1[start - 1] = temp;
 
                    // Swap until the characters
                    // are at same index
                    start--;
                    swap_count++;
                }
            }
        }
 
        // Print the minimum number of counts
        Console.WriteLine(swap_count);
    }
 
    // Driver Code
    public static void Main()
    {
        string S = "11112";
        int K = 4;
        minSwapsKthLargest(S, K);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
        function next_permutation(array)
        {
            var i = array.length - 1;
            while (i > 0 && array[i - 1].charCodeAt(0) >= array[i].charCodeAt(0)) {
                i--;
                 
            }
 
            if (i <= 0) {
                return false;
            }
 
            var j = array.length - 1;
 
            while (array[j].charCodeAt(0) <= array[i - 1].charCodeAt(0)) {
                j--;
            }
 
            var temp = array[i - 1];
            array[i - 1] = array[j];
            array[j] = temp;
 
            j = array.length - 1;
 
            while (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
 
            return array;
        }
 
        // Function to find the minimum number
        // of swaps required to make the Kth
        // smallest string greater than str
        function minSwapsKthLargest(str, k)
        {
         
            // Store the copy of the string
            let res = str.split('');
            str = str.split('')
 
            // Find the K-th permutation of
            // the given numeric string
            for (let i = 0; i < k; i++) {
                next_permutation(
                    str);
            }
 
            // Stores the count of swaps required
            let swap_count = 0;
 
            // Traverse the string and find the
            // swaps required greedily
            for (let i = 0; i < res.length; i++) {
 
                // If both characters do not match
                if (res[i] != str[i]) {
                    let start = i + 1;
 
                    // Search from i+1 index
                    while (res[i] != str[start]) {
 
                        // Find the index to swap
                        start++;
                    }
                    while (i != start) {
                        let temp = str[start];
                        str[start] = str[start - 1]
                        str[start - 1] = temp;
 
                        // Swap until the characters
                        // are at same index
                        start--;
                        swap_count++;
                    }
                }
            }
 
            // Print the minimum number of counts
            document.write(swap_count);
        }
 
        // Driver Code
        let S = "11112";
        let K = 4;
        minSwapsKthLargest(S, K);
 
    // This code is contributed by Potta Lokesh
    </script>

Output:

Time Complexity: O(N*(N + K))
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Greedy

Related
$Maximize sum of ratios of N given fractions by incrementing numerator and denominators K times by 1$ Maximize sum of ratios of N given fractions by incrementing numerator and denominators K times by 1
Maximum length of consecutive 1s or 0s after flipping at most K characters
Find Minimum Number Of Arrows Needed To Burst All Balloons
Minimize value of \|A - X\| + \|B - Y\| + \|C - Z\| such that X * Y = Z
Koko Eating Bananas

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13