Minimum number of flips or swaps of adjacent characters required to make two strings equal
Given two binary strings A and B of length N, the task is to count the minimum number of operations required to make the two given strings equal by either swapping adjacent characters or flipping any character of the string A.
Examples:
Input: A = β100β, B = β001β
Output: 2
Explanation: Flipping characters A[0](= β1β) and A[2](= β0β) modifies the string A to β001β, which is equal to the string B.Input: A = β0101β, B = β0011β
Output: 1
Explanation: Swapping the characters A[2](= β0β) and A[3](= β1β) modifies the string A to β0011β, which is equal to string B.
Approach: The problem can be solved using Dynamic Programming as it has Overlapping Subproblems and Optimal Substructure.
Follow the steps below to solve the problem:
- Initialize an array, say dp[] of size N+1 as {0}, where dp[i] stores the minimum number of operations required up to index i, to make the prefix of Ai equal to the prefix Bi.
- Iterate over the range [1, N] using a variable, say i, and performing the following operations:
- If A[i β 1] equals B[i β 1], then update dp[i] to dp[i β 1].
- Otherwise, update dp[i] to dp[i β 1] + 1.
- If swapping is possible, i.e. i > 1 and A[i β 2] is equal to B[i β 1] and A[i β 1] is equal to B[i β 2], then update dp[i] to min(dp[i], dp[i β 2] + 1).
- After completing the above steps, print the minimum number of operations obtained, i.e. the value dp[N].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the minimum // number of operations required // to make strings A and B equal int countMinSteps(string A, string B, int N) { // Stores all dp-states vector< int > dp(N + 1, 0); // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // If A[i - 1] equals to B[i - 1] if (A[i - 1] == B[i - 1]) { // Assign Dp[i - 1] to Dp[i] dp[i] = dp[i - 1]; } // Otherwise else { // Update dp[i] dp[i] = dp[i - 1] + 1; } // If swapping is possible if (i >= 2 && A[i - 2] == B[i - 1] && A[i - 1] == B[i - 2]) { // Update dp[i] dp[i] = min(dp[i], dp[i - 2] + 1); } } // Return the minimum // number of steps required return dp[N]; } // Driver Code int main() { // Given Input string A = "0101" ; string B = "0011" ; int N = A.length(); // Function Call cout << countMinSteps(A, B, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to count the minimum // number of operations required // to make strings A and B equal static int countMinSteps(String A, String B, int N) { // Stores all dp-states int [] dp = new int [N + 1 ]; for ( int i = 1 ; i <= N; i++) { // Update the value of A[i] dp[i] = 0 ; } // Iterate over the range [1, N] for ( int i = 1 ; i <= N; i++) { // If A[i - 1] equals to B[i - 1] if (A.charAt(i - 1 ) == B.charAt(i - 1 )) { // Assign Dp[i - 1] to Dp[i] dp[i] = dp[i - 1 ]; } // Otherwise else { // Update dp[i] dp[i] = dp[i - 1 ] + 1 ; } // If swapping is possible if (i >= 2 && A.charAt(i - 2 ) == B.charAt(i - 1 ) && A.charAt(i - 1 ) == B.charAt(i - 2 )) { // Update dp[i] dp[i] = Math.min(dp[i], dp[i - 2 ] + 1 ); } } // Return the minimum // number of steps required return dp[N]; } // Driver code public static void main(String[] args) { // Given Input String A = "0101" ; String B = "0011" ; int N = A.length(); // Function Call System.out.println(countMinSteps(A, B, N)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to count the minimum # number of operations required # to make strings A and B equal def countMinSteps(A, B, N) : # Stores all dp-states dp = [ 0 ] * (N + 1 ) # Iterate rate over the range [1, N] for i in range ( 1 , N + 1 ) : # If A[i - 1] equals to B[i - 1] if (A[i - 1 ] = = B[i - 1 ]) : # Assign Dp[i - 1] to Dp[i] dp[i] = dp[i - 1 ] # Otherwise else : # Update dp[i] dp[i] = dp[i - 1 ] + 1 # If swapping is possible if (i > = 2 and A[i - 2 ] = = B[i - 1 ] and A[i - 1 ] = = B[i - 2 ]) : # Update dp[i] dp[i] = min (dp[i], dp[i - 2 ] + 1 ) # Return the minimum # number of steps required return dp[N] # Driver Code # Given Input A = "0101" B = "0011" N = len (A) # Function Call print (countMinSteps(A, B, N)) # This code is contributed by splevel62. |
C#
// C# program for the above approach using System; class GFG{ // Function to count the minimum // number of operations required // to make strings A and B equal static int countMinSteps( string A, string B, int N) { // Stores all dp-states int [] dp = new int [N + 1]; for ( int i = 1; i <= N; i++) { // Update the value of A[i] dp[i] = 0; } // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // If A[i - 1] equals to B[i - 1] if (A[i - 1] == B[i - 1]) { // Assign Dp[i - 1] to Dp[i] dp[i] = dp[i - 1]; } // Otherwise else { // Update dp[i] dp[i] = dp[i - 1] + 1; } // If swapping is possible if (i >= 2 && A[i - 2] == B[i - 1] && A[i - 1] == B[i - 2]) { // Update dp[i] dp[i] = Math.Min(dp[i], dp[i - 2] + 1); } } // Return the minimum // number of steps required return dp[N]; } // Driver code public static void Main(String []args) { // Given Input string A = "0101" ; string B = "0011" ; int N = A.Length; // Function Call Console.Write(countMinSteps(A, B, N)); } } // This code is contributed by code_hunt |
Javascript
<script> // JavaScript Program for the above approach // Function to count the minimum // number of operations required // to make strings A and B equal function countMinSteps(A, B, N) { // Stores all dp-states let dp = new Array(N + 1).fill(0); // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { // If A[i - 1] equals to B[i - 1] if (A[i - 1] == B[i - 1]) { // Assign Dp[i - 1] to Dp[i] dp[i] = dp[i - 1]; } // Otherwise else { // Update dp[i] dp[i] = dp[i - 1] + 1; } // If swapping is possible if (i >= 2 && A[i - 2] == B[i - 1] && A[i - 1] == B[i - 2]) { // Update dp[i] dp[i] = Math.min(dp[i], dp[i - 2] + 1); } } // Return the minimum // number of steps required return dp[N]; } // Driver Code // Given Input let A = "0101" ; let B = "0011" ; let N = A.length; // Function Call document.write(countMinSteps(A, B, N)); // This code is contributed by Potta Lokesh </script> |
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Space optimization O(1)
In previous approach we the current value dp[i] is only depend upon the previous 2 values i.e. dp[i-1] and dp[i-2]. So to optimize the space we can keep track of previous and current values by the help of three variables prev1, prev2 and curr which will reduce the space complexity from O(N) to O(1).
Implementation Steps:
- Create 2 variables prev1 and prev2 to keep track o previous values of DP.
- Initialize base case prev1 = prev2 = 0.
- Create a variable curr to store current value.
- Iterate over subproblem using loop and update curr.
- After every iteration update prev1 and prev2 for further iterations.
- At last return curr.
Implementation:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the minimum // number of operations required // to make strings A and B equal int countMinSteps(string A, string B, int N) { // variables to Stores all dp-states int prev1 = 0, prev2 = 0, curr = 0; // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // If A[i - 1] equals to B[i - 1] if (A[i - 1] == B[i - 1]){ // Assign prev1 to curr curr = prev1; } else { // Update dp[i] curr = prev1 + 1; } // If swapping is possible if (i >= 2 && A[i - 2] == B[i - 1] && A[i - 1] == B[i - 2]){ // Update curr curr = min(curr, prev2 + 1); } // assigning values for further iteration prev2 = prev1; prev1 = curr; } // return answer return curr; } // Driver Code int main() { string A = "0101" ; string B = "0011" ; int N = A.length(); // function call cout << countMinSteps(A, B, N); return 0; } // --- by bhardwajji |
Java
import java.util.*; public class Main { // Function to count the minimum // number of operations required // to make strings A and B equal static int countMinSteps(String A, String B, int N) { // variables to Stores all dp-states int prev1 = 0 , prev2 = 0 , curr = 0 ; // Iterate over the range [1, N] for ( int i = 1 ; i <= N; i++) { // If A[i - 1] equals to B[i - 1] if (A.charAt(i - 1 ) == B.charAt(i - 1 )) { // Assign prev1 to curr curr = prev1; } else { // Update dp[i] curr = prev1 + 1 ; } // If swapping is possible if (i >= 2 && A.charAt(i - 2 ) == B.charAt(i - 1 ) && A.charAt(i - 1 ) == B.charAt(i - 2 )) { // Update curr curr = Math.min(curr, prev2 + 1 ); } // assigning values for further iteration prev2 = prev1; prev1 = curr; } // return answer return curr; } // Driver Code public static void main(String[] args) { String A = "0101" ; String B = "0011" ; int N = A.length(); // function call System.out.println(countMinSteps(A, B, N)); } } |
Python
def countMinSteps(A, B, N): # variables to Stores all dp-states prev1, prev2, curr = 0 , 0 , 0 # Iterate over the range [1, N] for i in range ( 1 , N + 1 ): # If A[i - 1] equals to B[i - 1] if A[i - 1 ] = = B[i - 1 ]: # Assign prev1 to curr curr = prev1 else : # Update dp[i] curr = prev1 + 1 # If swapping is possible if i > = 2 and A[i - 2 ] = = B[i - 1 ] and A[i - 1 ] = = B[i - 2 ]: # Update curr curr = min (curr, prev2 + 1 ) # assigning values for further iteration prev2, prev1 = prev1, curr # return answer return curr # Driver Code A = "0101" B = "0011" N = len (A) # function call print (countMinSteps(A, B, N)) |
C#
// C# program for the above approach using System; public class GFG { // Function to count the minimum // number of operations required // to make strings A and B equal public static int CountMinSteps( string A, string B, int N) { // Variables to store all dp-states int prev1 = 0, prev2 = 0, curr = 0; // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // If A[i - 1] equals to B[i - 1] if (A[i - 1] == B[i - 1]) { // Assign prev1 to curr curr = prev1; } else { // Update dp[i] curr = prev1 + 1; } // If swapping is possible if (i >= 2 && A[i - 2] == B[i - 1] && A[i - 1] == B[i - 2]) { // Update curr curr = Math.Min(curr, prev2 + 1); } // Assigning values for further iteration prev2 = prev1; prev1 = curr; } // Return the answer return curr; } // Driver Code public static void Main( string [] args) { string A = "0101" ; string B = "0011" ; int N = A.Length; // Function call Console.WriteLine(CountMinSteps(A, B, N)); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript program for the above approach // Function to count the minimum number of operations required // to make strings A and B equal function countMinSteps(A, B, N) { // Variables to store all dp states let prev1 = 0; let prev2 = 0; let curr = 0; // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { // If A[i - 1] equals B[i - 1] if (A[i - 1] === B[i - 1]) { // Assign prev1 to curr curr = prev1; } else { // Update dp[i] curr = prev1 + 1; } // If swapping is possible if (i >= 2 && A[i - 2] === B[i - 1] && A[i - 1] === B[i - 2]) { // Update curr curr = Math.min(curr, prev2 + 1); } // Assigning values for further iteration prev2 = prev1; prev1 = curr; } // Return the answer return curr; } // Driver Code const A = "0101" ; const B = "0011" ; const N = A.length; // Function call document.write(countMinSteps(A, B, N)); // This code is contributed by Susobhan Akhuli |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us