Minimum swaps required between two strings to make one string strictly greater than the other
Given two strings A and B of length M and N respectively, the task is to find the minimum swapping of two characters required to make string A lexicographically greater than the string B.
Examples:
Input: A = β1432β, B = β789β, M = 4, N = 3
Output: 1
Explanation:
One possible way is to swap characters at index 0 of both the strings. Therefore, A modifies to β7432β and B modifies to β189β.Input: A = β3733β, B = β3333β, M = 4, N = 4
Output: 2
Explanation:
Step 1:Swap character at index 1 of string A with character at index 0 of string B. The strings A and B are modified to β3333β and β7333β.
Step 2: Swap the character at index 0 of string A with a character at index 0 of string B. The strings A and B are modified to β7333β and β3333β.
Approach: It can be observed that if M ? N and all the characters are the same, including both strings, then it is not possible to make string A strictly greater than string B. Otherwise, string A can be made strictly greater than string B by placing the two different characters at the 0th index of both strings in a maximum of two moves.
Follow the steps below to solve the problem:
- First, check if the first character of string A is greater than the first character of string B then print 0.
- Otherwise, check if B[0] > A[0] then 1 swap is needed, so swap A[0] with B[0] and print 1.
- Otherwise, check if all the characters are the same in both strings and M ? N then it is not possible, so print -1.
- Otherwise, check if there lies any character in A which is smaller than A[0] or a character in B which is greater than B[0] then print 1.
- Otherwise, check if there exists any character in A which is less than A[0] or any character in B which is greater than B[0] then print 2.
- Otherwise, return 0 if none of the above conditions satisfies.
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 steps to make A > B int minSteps(string A, string B, int M, int N) { if (A[0] > B[0]) return 0; if (B[0] > A[0]) { return 1; } // If all character are same and M <= N if (M <= N && A[0] == B[0] && count(A.begin(), A.end(), A[0]) == M && count(B.begin(), B.end(), B[0]) == N) return -1; // If there lies any character // in B which is greater than B[0] for ( int i = 1; i < N; i++) { if (B[i] > B[0]) return 1; } // If there lies any character // in A which is smaller than A[0] for ( int i = 1; i < M; i++) { if (A[i] < A[0]) return 1; } // If there lies a character which // is in A and greater than A[0] for ( int i = 1; i < M; i++) { if (A[i] > A[0]) { swap(A[i], B[0]); swap(A[0], B[0]); return 2; } } // If there lies a character which // is in B and less than B[0] for ( int i = 1; i < N; i++) { if (B[i] < B[0]) { swap(A[0], B[i]); swap(A[0], B[0]); return 2; } } // Otherwise return 0; } // Driver Code int main() { string A = "adsfd" ; string B = "dffff" ; int M = A.length(); int N = B.length(); cout << minSteps(A, B, M, N); return 0; } |
Java
// Java program for above approach import java.util.*; import java.lang.*; class GFG { // Function to find the minimum // number of steps to make A > B static int minSteps(StringBuilder A, StringBuilder B, int M, int N) { if (A.charAt( 0 ) > B.charAt( 0 )) return 0 ; if (B.charAt( 0 ) > A.charAt( 0 )) { return 1 ; } // If all character are same and M <= N if (M <= N && A.charAt( 0 ) == B.charAt( 0 ) && count(A, A.charAt( 0 )) == M && count(B, B.charAt( 0 )) == N) return - 1 ; // If there lies any character // in B which is greater than B[0] for ( int i = 1 ; i < N; i++) { if (B.charAt(i) > B.charAt( 0 )) return 1 ; } // If there lies any character // in A which is smaller than A[0] for ( int i = 1 ; i < M; i++) { if (A.charAt(i) < A.charAt( 0 )) return 1 ; } // If there lies a character which // is in A and greater than A[0] for ( int i = 1 ; i < M; i++) { if (A.charAt(i) > A.charAt( 0 )) { swap(A, i, B, 0 ); swap(A, 0 , B, 0 ); return 2 ; } } // If there lies a character which // is in B and less than B[0] for ( int i = 1 ; i < N; i++) { if (B.charAt(i) < B.charAt( 0 )) { swap(A, 0 , B, i); swap(A, 0 , B, 0 ); return 2 ; } } // Otherwise return 0 ; } static int count(StringBuilder a, char c) { int count = 0 ; for ( int i = 0 ; i < a.length(); i++) if (a.charAt(i) == c) count++; return count; } static void swap(StringBuilder s1, int index1, StringBuilder s2, int index2) { char c = s1.charAt(index1); s1.setCharAt(index1,s2.charAt(index2)); s2.setCharAt(index2,c); } // Driver function public static void main (String[] args) { StringBuilder A = new StringBuilder( "adsfd" ); StringBuilder B = new StringBuilder( "dffff" ); int M = A.length(); int N = B.length(); System.out.println(minSteps(A, B, M, N)); } } // This code is contributed by offbeat. |
Python3
# Python3 program for the above approach # Function to find the minimum # number of steps to make A > B def minSteps(A, B, M, N): if (A[ 0 ] > B[ 0 ]): return 0 if (B[ 0 ] > A[ 0 ]): return 1 # If all character are same and M <= N if (M < = N and A[ 0 ] = = B[ 0 ] and A.count(A[ 0 ]) = = M and B.count(B[ 0 ]) = = N): return - 1 # If there lies any character # in B which is greater than B[0] for i in range ( 1 , N): if (B[i] > B[ 0 ]): return 1 # If there lies any character # in A which is smaller than A[0] for i in range ( 1 , M): if (A[i] < A[ 0 ]): return 1 # If there lies a character which # is in A and greater than A[0] for i in range ( 1 , M): if (A[i] > A[ 0 ]): A[ 0 ], B[i] = B[i], A[ 0 ] A[ 0 ], B[ 0 ] = B[ 0 ], A[ 0 ] return 2 # If there lies a character which # is in B and less than B[0] for i in range ( 1 , N): if (B[i] < B[ 0 ]): A[ 0 ], B[i] = B[i], A[ 0 ] A[ 0 ], B[ 0 ] = B[ 0 ], A[ 0 ] return 2 # Otherwise return 0 # Driver Code if __name__ = = '__main__' : A = "adsfd" B = "dffff" M = len (A) N = len (B) print (minSteps(A, B, M, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for above approach using System; using System.Text; public class GFG { // Function to find the minimum // number of steps to make A > B static int minSteps(StringBuilder A, StringBuilder B, int M, int N) { if (A[0] > B[0]) return 0; if (B[0] > A[0]) { return 1; } // If all character are same and M <= N if (M <= N && A[0] == B[0] && count(A, A[0]) == M && count(B, B[0]) == N) return -1; // If there lies any character // in B which is greater than B[0] for ( int i = 1; i < N; i++) { if (B[i] > B[0]) return 1; } // If there lies any character // in A which is smaller than A[0] for ( int i = 1; i < M; i++) { if (A[i] < A[0]) return 1; } // If there lies a character which // is in A and greater than A[0] for ( int i = 1; i < M; i++) { if (A[i] > A[0]) { swap(A, i, B, 0); swap(A, 0, B, 0); return 2; } } // If there lies a character which // is in B and less than B[0] for ( int i = 1; i < N; i++) { if (B[i] < B[0]) { swap(A, 0, B, i); swap(A, 0, B, 0); return 2; } } // Otherwise return 0; } static int count(StringBuilder a, char c) { int count = 0; for ( int i = 0; i < a.Length; i++) if (a[i] == c) count++; return count; } static void swap(StringBuilder s1, int index1, StringBuilder s2, int index2) { char c = s1[index1]; s1[index1] = s2[index2]; s2[index2] = c; } // Driver function static public void Main () { StringBuilder A = new StringBuilder( "adsfd" ); StringBuilder B = new StringBuilder( "dffff" ); int M=A.Length; int N=B.Length; Console.WriteLine(minSteps(A, B, M, N)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> //Javascript program to implement // the above approach // Function to find the minimum // number of steps to make A > B function minSteps( A, B,M, N) { if (A[0] > B[0]) return 0; if (B[0] > A[0]) { return 1; } // If all character are same and M <= N if (M <= N && A[0] == B[0] && count(A, A[0]) == M && count(B, B[0]) == N) return -1; // If there lies any character // in B which is greater than B[0] for ( var i = 1; i < N; i++) { if (B[i] > B[0]) return 1; } // If there lies any character // in A which is smaller than A[0] for ( var i = 1; i < M; i++) { if (A[i] < A[0]) return 1; } // If there lies a character which // is in A and greater than A[0] for ( var i = 1; i < M; i++) { if (A[i] > A[0]) { swap(A, i, B, 0); swap(A, 0, B, 0); return 2; } } // If there lies a character which // is in B and less than B[0] for ( var i = 1; i < N; i++) { if (B[i] < B[0]) { swap(A, 0, B, i); swap(A, 0, B, 0); return 2; } } // Otherwise return 0; } function count(a, c) { count = 0; for ( var i = 0; i < a.length; i++) if (a[i] == c) count++; return count; } function swap(s1, index1, s2, index2) { var c = s1[index1]; s1[index1] = s2[index2]; s2[index2] = c; } var A = "adsfd" ; var B = "dffff" ; var M = A.length; var N = B.length; document.write(minSteps(A, B, M, N)); // This code is contributed by SoumikMondal </script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)