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 equalint 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 Codeint 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 approachimport java.io.*;class GFG{ // Function to count the minimum// number of operations required// to make strings A and B equalstatic 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 codepublic 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 equaldef 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 InputA = "0101"B = "0011"N = len(A)# Function Callprint(countMinSteps(A, B, N))# This code is contributed by splevel62. |
C#
// C# program for the above approachusing System;class GFG{// Function to count the minimum// number of operations required// to make strings A and B equalstatic 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 codepublic 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> |
Output
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 equalint 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 Codeint 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 CodeA = "0101"B = "0011"N = len(A)# function callprint(countMinSteps(A, B, N)) |
C#
// C# program for the above approachusing 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 |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
