Minimizing the cost to convert A to B with Flips
Given two binary strings A and B both of the same length and two integers x and y. In one operation, we can select two indices l and r and flip the number at A[l] and A[r] i.e. 1 to 0 and 0 to 1. If l+1 = r, the cost of this operation is x, otherwise the cost is y. The task is to find the minimum cost to convert A to B by applying the above operations or print -1 if it is impossible to do so.
Examples:
Input: A = “01001”, B = “00101”, x = 8, y = 9
Output: 8
Explanation: select indices 1 and 2 and apply the operation which costs 8Input: A = “10000011000001”, B = “00000000000000”, x = 8, y = 9
Output: 17
Explanation: Select indices 6 and 7 and apply the operation, so cost = 8 and select index 0 and 13 and apply the operation with cost = 9. So total cost = 8 + 9 = 17Input: A = “01000”, B = “11011”, x = 7, y = 2
Output: -1
Explanation: It is impossible to convert string a to b
Approach: To solve the problem, follow the below idea:
The approach is to use Dynamic programming to find the minimum cost of converting string a to string b by applying the specified operations.
Steps to solve the problem:
- Define a recursive function, say solve(idx, flag) to calculate the minimum cost to convert the substring of A starting from index idx to the corresponding substring of B.
- The flag is true if we have already changed some character before with a cost of y and now, we can change this character without any cost.
- Maintain a vector v to store all the indices where the character in A differs from B.
- At any index i, we have 2 choices:
- Choice 1: Change the current index and the next index by changing adjacent bits starting from v[idx] to v[idx+1] and incurring a cost of (v[idx + 1] – v[idx]) * x
- Choice 2: Change the current index with cost = y and move to the next index with the advantage of changing any other index in future free of cost.
- Explore all the choices and return the answer as dp[0][0].
Below is the code for the above approach:
C++
#include <bits/stdc++.h> #define ll long long using namespace std; const ll N = 5e3 + 15; // dp table for memoization ll dp[N][2]; ll n, x, y, z; string A, B; // vector to store indices which differ in string A and B vector<ll> v; ll solve(ll idx, bool flag) { if (idx > z) return 1e10; if (idx == z) return 0; if (dp[idx][flag] != -1) return dp[idx][flag]; ll cost = 0; // If the current index is not the last index of A if (idx + 1 < z) { // We cannot change the current index free of cost if (!flag) cost = min(solve(idx + 1, 1) + y, solve(idx + 2, 0) + (v[idx + 1] - v[idx]) * x); // We can change the current index free of cost else cost = min(solve(idx + 1, 0), solve(idx + 2, 1) + (v[idx + 1] - v[idx]) * x); } // If the current index is the last index of A else { // We have to change the current index with some // previous operation cost = solve(idx + 1, 0); } return dp[idx][flag] = cost; } int main() { A = "10000011000001" ; B = "00000000000000" ; x = 8; y = 9; n = A.size(); for (ll i = 0; i < n; i++) if (A[i] != B[i]) v.push_back(i); z = v.size(); // If the number of different indices is odd, then it is // impossible to convert A to B if (z % 2) { cout << -1; } else { for ( int i = 0; i <= z; i++) { dp[i][1] = dp[i][0] = -1; } cout << solve(0, 0); } return 0; } |
Java
import java.util.*; public class Solution { static int N = 5 * 1000 + 15 ; static int [][] dp = new int [N][ 2 ]; static int n, x, y, z; static String A, B; static int [] v; static int solve( int idx, int flag) { if (idx > z) { return ( int )1e10; } if (idx == z) { return 0 ; } if (dp[idx][flag] != - 1 ) { return dp[idx][flag]; } int cost = 0 ; // If the current index is not the last index of A if (idx + 1 < z) { if (flag == 0 ) { // We cannot change the current index free // of cost cost = Math.min(solve(idx + 1 , 1 ) + y, solve(idx + 2 , 0 ) + (v[idx + 1 ] - v[idx]) * x); } else { // We can change the current index free of // cost cost = Math.min(solve(idx + 1 , 0 ), solve(idx + 2 , 1 ) + (v[idx + 1 ] - v[idx]) * x); } } else { // If the current index is the last index of A // We have to change the current index with some // previous operation cost = solve(idx + 1 , 0 ); } dp[idx][flag] = cost; return cost; } public static void main(String[] args) { A = "10000011000001" ; B = "00000000000000" ; x = 8 ; y = 9 ; n = A.length(); v = new int [n]; // Populating the array 'v' with indices where A and // B differ int count = 0 ; for ( int i = 0 ; i < n; i++) { if (A.charAt(i) != B.charAt(i)) { v[count++] = i; } } z = count; // If the number of different indices is odd, then // it is impossible to convert A to B if (z % 2 == 1 ) { System.out.println(- 1 ); } else { // Initializing the dp array with -1 for ( int i = 0 ; i <= z; i++) { Arrays.fill(dp[i], - 1 ); } // Printing the result of the solve function System.out.println(solve( 0 , 0 )); } } } |
Python3
import sys sys.setrecursionlimit( 10 * * 6 ) N = 5 * 10 * * 3 + 15 # dp table for memoization dp = [[ - 1 , - 1 ] for _ in range (N)] n, x, y, z = 0 , 0 , 0 , 0 A, B = " ", " " # vector to store indices which differ in string A and B v = [] def solve(idx, flag): global dp, x, y, z, v if idx > z: return 1e10 if idx = = z: return 0 if dp[idx][flag] ! = - 1 : return dp[idx][flag] cost = 0 # If the current index is not the last index of A if idx + 1 < z: # We cannot change the current index free of cost if not flag: cost = min (solve(idx + 1 , 1 ) + y, solve(idx + 2 , 0 ) + (v[idx + 1 ] - v[idx]) * x) # We can change the current index free of cost else : cost = min (solve(idx + 1 , 0 ), solve(idx + 2 , 1 ) + (v[idx + 1 ] - v[idx]) * x) # If the current index is the last index of A else : # We have to change the current index with some # previous operation cost = solve(idx + 1 , 0 ) dp[idx][flag] = cost return cost def main(): global A, B, x, y, n, v, z, dp A = "10000011000001" B = "00000000000000" x = 8 y = 9 n = len (A) for i in range (n): if A[i] ! = B[i]: v.append(i) z = len (v) # If the number of different indices is odd, then it is # impossible to convert A to B if z % 2 : print ( - 1 ) else : for i in range (z + 1 ): dp[i][ 1 ] = dp[i][ 0 ] = - 1 print (solve( 0 , 0 )) if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; class Program { const int N = 5_015; // dp table for memoization static long [,] dp = new long [N, 2]; static int n, x, y, z; static string A, B; // vector to store indices which differ in string A and B static List< int > v = new List< int >(); static long Solve( int idx, bool flag) { if (idx > z) return ( long )1e10; if (idx == z) return 0; if (dp[idx, Convert.ToInt32(flag)] != -1) return dp[idx, Convert.ToInt32(flag)]; long cost = 0; // If the current index is not the last index of A if (idx + 1 < z) { // We cannot change the current index free of cost if (!flag) cost = Math.Min(Solve(idx + 1, true ) + y, Solve(idx + 2, false ) + (v[idx + 1] - v[idx]) * x); // We can change the current index free of cost else cost = Math.Min(Solve(idx + 1, false ), Solve(idx + 2, true ) + (v[idx + 1] - v[idx]) * x); } // If the current index is the last index of A else { // We have to change the current index with some // previous operation cost = Solve(idx + 1, false ); } return dp[idx, Convert.ToInt32(flag)] = cost; } static void Main() { A = "10000011000001" ; B = "00000000000000" ; x = 8; y = 9; n = A.Length; for ( int i = 0; i < n; i++) if (A[i] != B[i]) v.Add(i); z = v.Count; // If the number of different indices is odd, then it is // impossible to convert A to B if (z % 2 != 0) { Console.WriteLine(-1); } else { for ( int i = 0; i <= z; i++) { dp[i, 1] = dp[i, 0] = -1; } Console.WriteLine(Solve(0, false )); } } } |
Javascript
const N = 5 * 10**3 + 15; // dp table for memoization const dp = Array.from({ length: N }, () => Array(2).fill(-1)); let n, x, y, z; let A, B; // vector to store indices which differ in string A and B let v = []; function solve(idx, flag) { if (idx > z) { return 1e10; } if (idx === z) { return 0; } if (dp[idx][flag] !== -1) { return dp[idx][flag]; } let cost = 0; // If the current index is not the last index of A if (idx + 1 < z) { // We cannot change the current index free of cost if (!flag) { cost = Math.min(solve(idx + 1, 1) + y, solve(idx + 2, 0) + (v[idx + 1] - v[idx]) * x); } // We can change the current index free of cost else { cost = Math.min(solve(idx + 1, 0), solve(idx + 2, 1) + (v[idx + 1] - v[idx]) * x); } } // If the current index is the last index of A else { // We have to change the current index with some // previous operation cost = solve(idx + 1, 0); } dp[idx][flag] = cost; return cost; } A = "10000011000001" ; B = "00000000000000" ; x = 8; y = 9; n = A.length; for (let i = 0; i < n; i++) { if (A[i] !== B[i]) { v.push(i); } } z = v.length; // If the number of different indices is odd, then it is // impossible to convert A to B if (z % 2) { console.log(-1); } else { for (let i = 0; i <= z; i++) { dp[i][1] = dp[i][0] = -1; } console.log(solve(0, 0)); } |
17
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us