We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Apply Operations to Make Two Strings Equal

Number: 3033

Difficulty: Medium

Paid? No

Companies: Google, Zeta

Problem Description

You are given two 0-indexed binary strings s1 and s2 (both of length n) and a positive integer x. You may perform the following operations on s1 any number of times:

  1. Pick any two indices i and j and flip both s1[i] and s1[j] at a cost of x.
  2. Pick an index i (with i < n - 1) and flip both s1[i] and s1[i + 1] at a cost of 1.

Flipping means converting a '0' to a '1' or vice versa. Return the minimum cost to make s1 equal to s2 or -1 if it is impossible.

Key Insights

  • Since every operation flips exactly two bits, the total number of mismatches between s1 and s2 must be even; otherwise the answer is -1.
  • Extract the list of indices where s1 and s2 differ. These positions must be paired up and “fixed” together.
  • There are two ways to pair two mismatches: • Use the arbitrary-pair operation (cost = x). This is always available. • If the two mismatches occur at consecutive positions in s1 (i.e. index j == index i + 1), an adjacent flip (cost = 1) can fix them.
  • For two mismatches (only a pair), the answer is: • If the two indices are consecutive, answer = min(x, 1) (remember x is a positive integer so usually this gives 1 if x > 1). • Otherwise, answer = x.
  • For more than 2 mismatches, notice that the optimal pairing is not necessarily to pair adjacent differences in the extracted list—instead one should compute a minimum-cost non-crossing matching. This can be solved with interval dynamic programming, where for a subarray of difference indices we try pairing the first index with any other index to “divide” the problem into independent subproblems.

Space and Time Complexity

Time Complexity: O(m^3) in the worst case (where m is the number of mismatches and m ≤ n, with n up to 500). In practice, m is often much smaller. Space Complexity: O(m^2) for the DP table.

Solution

We first compute the list of positions (diff) where s1 and s2 differ. If the number of mismatches is odd, return -1 immediately.

If there are exactly two mismatches, check if they are consecutive:  • If yes, the cost is min(1, x) (adjacent operation costs 1 which is optimal if x > 1).  • Otherwise, the only option is to flip both arbitrarily at cost x.

When there are more than two mismatches, we use interval DP. Let F(l, r) denote the minimum cost to pair all mismatch indices between positions l and r in the diff list (with l ≤ r and the number of indices in the interval even). For a chosen pair between diff[l] and diff[k] (where k ranges from l+1 to r and k - l is odd), the cost to fix that pair is:  • 1 if diff[k] == diff[l] + 1 (i.e. the mismatches are adjacent in s1, so an adjacent flip can repair them).  • Otherwise, cost is x using the arbitrary-two operation. Then we add F(l+1, k-1) for the indices between the paired ones and F(k+1, r) for the remaining tail. We take the minimum over all valid choices.

This non-crossing matching DP covers all possibilities and handles cases where pairing “inside” mismatches differently leads to a lower cost.

Code Solutions

# Python Solution
import math

def minimumCost(s1: str, s2: str, x: int) -> int:
    n = len(s1)
    # Collect indices where s1 and s2 differ.
    diff = [i for i in range(n) if s1[i] != s2[i]]
    m = len(diff)
    
    # If the number of mismatches is odd, it's impossible.
    if m % 2 == 1:
        return -1
    # Base case: no mismatches.
    if m == 0:
        return 0
    # Special case for exactly two mismatches.
    if m == 2:
        if diff[1] == diff[0] + 1:
            return min(1, x)
        else:
            return x
    
    # dp[l][r]: minimum cost to pair differences in diff[l...r]
    dp = [[math.inf]*(m) for _ in range(m)]
    
    # For intervals of length 0 (empty), cost is 0.
    # We fill dp over intervals; use gap-based DP.
    for length in range(2, m+1, 2):  # Only even lengths are valid.
        for l in range(0, m - length + 1):
            r = l + length - 1
            # Try pairing diff[l] with every valid partner diff[k]
            for k in range(l+1, r+1, 2):  # k must be chosen to keep even count on left side.
                # cost to fix the pair (diff[l], diff[k])
                if diff[k] == diff[l] + 1:
                    cost_pair = 1   # Use adjacent flip operation.
                else:
                    cost_pair = x   # Use arbitrary-pair operation.
                # cost for the inside and outside intervals
                left_cost = dp[l+1][k-1] if k-1 >= l+1 else 0
                right_cost = dp[k+1][r] if k+1 <= r else 0
                dp[l][r] = min(dp[l][r], cost_pair + left_cost + right_cost)
    
    return dp[0][m-1]

# Example test cases
print(minimumCost("1100011000", "0101001010", 2))  # Expected output: 4
print(minimumCost("10110", "00011", 4))             # Expected output: -1
← Back to All Questions