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 Kth smallest numeric string greater than the given string.
Examples:
Input: S = “11112”, K = 4
Output: 4
Explanation:
The Kth(= 4th) 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 strvoid 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 Codeint main(){ string S = "11112"; int K = 4; minSwapsKthLargest(S, K); return 0;} |
Java
// Java program for the above approachimport 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 approachdef 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 strdef 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 CodeS = "11112"K = 4minSwapsKthLargest(S, K)# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing 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:
4
Time Complexity: O(N*(N + K))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
