LeetCode 2896 - Apply Operations to Make Two Strings Equal

We are given two binary strings, s1 and s2, of the same length n, along with a positive integer x. Our goal is to transform s1 into s2 using the minimum possible cost. We are allowed to perform two kinds of operations: 1. Choose any two positions i and j, then flip both bits.

leetcodemediumstringdynamic-programming

LeetCode Problem 2896

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming

Solution

LeetCode 2896 - Apply Operations to Make Two Strings Equal

Problem Understanding

We are given two binary strings, s1 and s2, of the same length n, along with a positive integer x.

Our goal is to transform s1 into s2 using the minimum possible cost. We are allowed to perform two kinds of operations:

  1. Choose any two positions i and j, then flip both bits. This operation costs x.
  2. Choose two adjacent positions i and i + 1, then flip both bits. This operation costs 1.

A flip changes 0 to 1 and 1 to 0.

The important observation is that we do not care about the actual values in the strings. Instead, we only care about positions where the strings differ. Let us define a mismatch position as an index where s1[i] != s2[i].

Each operation flips exactly two positions. Therefore, every operation changes the mismatch status of exactly two indices. This immediately implies that the total number of mismatches must be even. If the mismatch count is odd, it is impossible to eliminate all mismatches, and the answer is -1.

The constraints are relatively small:

  • 1 ≤ n ≤ 500
  • 1 ≤ x ≤ 500

A size of 500 is large enough that brute force over all possible operation sequences is infeasible, but small enough that a dynamic programming solution with roughly quadratic complexity is practical.

Some important edge cases include:

  • No mismatches at all, answer is 0.
  • An odd number of mismatches, answer is -1.
  • Very small strings such as length 1.
  • Cases where adjacent operations are cheaper than the global operation.
  • Cases where the global operation is cheaper than repeatedly moving mismatches together using adjacent flips.

Approaches

Brute Force

A brute force solution would treat every reachable string as a state and try all possible operations from each state.

From a given string, we could:

  • Apply the cost x operation to every pair of indices.
  • Apply the cost 1 operation to every adjacent pair.

This creates an enormous state graph. Since there are 2^n possible binary strings, even for moderate values of n the state space becomes completely intractable.

Although shortest path algorithms such as Dijkstra's algorithm would eventually find the optimal answer, the number of states grows exponentially, making this approach impossible for n ≤ 500.

Key Insight

Instead of tracking the entire string, focus only on mismatch positions.

Let:

pos = indices where s1[i] != s2[i]

Suppose there are m mismatches.

Every operation flips two positions, so mismatches must ultimately be paired and eliminated.

For two mismatch positions:

  • We can directly fix them using the first operation with cost x.
  • We can move one mismatch toward the other using adjacent operations. If the mismatches are at positions a and b, the cost is b - a.

Therefore, when pairing two mismatches, the effective cost is:

min(x, distance)

However, pairings interact with one another. Choosing one pair affects which mismatches remain available later.

This leads naturally to interval dynamic programming on the mismatch positions.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores reachable string states
Optimal DP O(m²) O(m²) Interval DP on mismatch positions

Where m is the number of mismatch positions and m ≤ n.

Algorithm Walkthrough

Step 1: Find mismatch positions

Create an array:

pos = [i for i where s1[i] != s2[i]]

Only these positions matter.

Step 2: Check feasibility

If the number of mismatches is odd, return -1.

Each operation flips exactly two positions, so parity can never change.

Step 3: Handle trivial case

If there are no mismatches, return 0.

The strings are already equal.

Step 4: Define DP state

Let:

dp(l, r)

represent the minimum cost required to eliminate all mismatches between indices l and r in the mismatch array.

The interval contains:

pos[l], pos[l+1], ..., pos[r]

Only intervals with an even number of mismatches are valid.

Step 5: Pair the leftmost mismatch

Consider mismatch l.

To eliminate it, it must be paired with some other mismatch k where:

l < k ≤ r

The cost of pairing them is:

pair_cost = min(x, pos[k] - pos[l])

After pairing l and k, the remaining mismatches split into two independent intervals:

(l+1, k-1)
(k+1, r)

Therefore:

dp(l, r) =
min(
    pair_cost
    + dp(l+1, k-1)
    + dp(k+1, r)
)

over all valid choices of k.

Step 6: Memoize results

Many intervals repeat during recursion.

Store computed values so each interval is solved only once.

Step 7: Return answer

The final answer is:

dp(0, m-1)

where m is the number of mismatches.

Why it works

Every mismatch must eventually be paired with exactly one other mismatch because each operation affects two positions. The dynamic programming state considers all possible valid pairings for the leftmost mismatch in an interval. Once a pair is chosen, the remaining mismatches form independent subproblems. Since every valid pairing structure is explored exactly once and the minimum cost is taken, the DP computes the globally optimal solution.

Python Solution

from functools import lru_cache

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        pos = [i for i, (a, b) in enumerate(zip(s1, s2)) if a != b]
        m = len(pos)

        if m % 2:
            return -1

        if m == 0:
            return 0

        @lru_cache(None)
        def dp(left: int, right: int) -> int:
            if left > right:
                return 0

            answer = float("inf")

            for k in range(left + 1, right + 1, 2):
                pair_cost = min(x, pos[k] - pos[left])

                answer = min(
                    answer,
                    pair_cost
                    + dp(left + 1, k - 1)
                    + dp(k + 1, right)
                )

            return answer

        return dp(0, m - 1)

Implementation Explanation

The first step constructs the mismatch array pos. Every index in this array represents a location where the two strings currently differ.

If the mismatch count is odd, the function immediately returns -1. No sequence of operations can change the parity of the mismatch count.

The memoized recursive function dp(left, right) solves the interval bounded by mismatch indices left and right.

For every possible partner k of the leftmost mismatch, the algorithm computes the cost of pairing those two mismatches. The cost is the cheaper of:

  • One global operation costing x.
  • Moving a mismatch across the interval using adjacent operations, costing the distance between positions.

After choosing a pair, the remaining mismatches split into two independent intervals. The recursive costs of those intervals are added to the current pairing cost.

Memoization ensures each interval is solved only once.

Go Solution

import "math"

func minOperations(s1 string, s2 string, x int) int {
	pos := []int{}

	for i := 0; i < len(s1); i++ {
		if s1[i] != s2[i] {
			pos = append(pos, i)
		}
	}

	m := len(pos)

	if m%2 == 1 {
		return -1
	}

	if m == 0 {
		return 0
	}

	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, m)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}

	var dp func(int, int) int

	dp = func(left, right int) int {
		if left > right {
			return 0
		}

		if memo[left][right] != -1 {
			return memo[left][right]
		}

		ans := math.MaxInt32

		for k := left + 1; k <= right; k += 2 {
			pairCost := x
			dist := pos[k] - pos[left]

			if dist < pairCost {
				pairCost = dist
			}

			cost := pairCost +
				dp(left+1, k-1) +
				dp(k+1, right)

			if cost < ans {
				ans = cost
			}
		}

		memo[left][right] = ans
		return ans
	}

	return dp(0, m-1)
}

Go Specific Notes

The Go implementation mirrors the Python solution closely. Since Go does not provide built in memoization decorators, a two dimensional slice is used to cache interval results. Entries initialized to -1 indicate unsolved states. Integer overflow is not a concern because the maximum possible answer is well below the range of a 32 bit integer.

Worked Examples

Example 1

s1 = "1100011000"
s2 = "0101001010"
x = 2

Mismatch positions:

Index Mismatch
0 Yes
3 Yes
4 Yes
8 Yes

So:

pos = [0, 3, 4, 8]

We solve:

dp(0,3)

Possible pairings of position 0:

Pair Cost
(0,3) min(2,3)=2
(0,4) min(2,4)=2
(0,8) min(2,8)=2

Evaluate:

Pair (0,3)

cost = 2 + dp(1,0) + dp(2,3)

For dp(2,3):

cost = min(2, 8-4)
     = 2

Total:

2 + 2 = 4

Pair (0,4)

cost = 2 + dp(1,1) + dp(3,3)

Invalid because unmatched intervals remain.

Pair (0,8)

cost = 2 + dp(1,2)

For dp(1,2):

min(2, 4-3)
= 1

Total:

2 + 1 = 3

The DP finds the minimum valid arrangement and returns:

4

Example 2

s1 = "10110"
s2 = "00011"

Mismatch positions:

[0, 2, 3]

Count:

3

Odd number of mismatches.

Therefore:

answer = -1

Complexity Analysis

Measure Complexity Explanation
Time O(m²) Each interval state is solved once
Space O(m²) Memoization table for interval states

Here m is the number of mismatch positions. Since m ≤ n ≤ 500, the worst case remains manageable. The interval DP contains O(m²) states, and memoization prevents repeated computation of the same subproblems.

Test Cases

sol = Solution()

assert sol.minOperations("1100011000", "0101001010", 2) == 4  # example 1
assert sol.minOperations("10110", "00011", 4) == -1  # example 2

assert sol.minOperations("0", "0", 5) == 0  # already equal
assert sol.minOperations("1", "0", 5) == -1  # single mismatch

assert sol.minOperations("00", "11", 1) == 1  # adjacent pair
assert sol.minOperations("00", "11", 10) == 1  # adjacent cheaper than x

assert sol.minOperations("1001", "0110", 2) == 2  # direct pairing
assert sol.minOperations("1001", "0110", 10) == 2  # use adjacent movement

assert sol.minOperations("1111", "0000", 3) == 2  # two adjacent fixes

assert sol.minOperations("010101", "101010", 2) >= 0  # many mismatches

assert sol.minOperations("000000", "000000", 1) == 0  # all equal

Test Summary

Test Why
Example 1 Verifies official optimal answer
Example 2 Verifies odd mismatch detection
"0" vs "0" No work required
"1" vs "0" Single mismatch impossible
"00" vs "11" with small x Adjacent operation usage
"00" vs "11" with large x Distance based choice
"1001" vs "0110" Pairing mismatches correctly
Same case with large x Ensures cost minimization
"1111" vs "0000" Multiple pairs
Alternating strings Stress pairing logic
Identical strings Zero cost path

Edge Cases

Odd Number of Mismatches

An odd mismatch count is impossible to resolve because every allowed operation flips exactly two positions. A buggy implementation might attempt to continue processing and produce an invalid answer. The solution explicitly checks parity before starting the DP and immediately returns -1.

Strings Already Equal

When there are no mismatch positions, the mismatch array is empty. Without a special check, some implementations may attempt to access invalid indices in the DP. The solution handles this case directly and returns 0.

Large Global Cost

If x is much larger than the distance between mismatches, repeatedly using adjacent operations can be cheaper. The algorithm handles this naturally by using:

min(x, pos[k] - pos[left])

for every potential pair.

Small Global Cost

If x is very small, pairing distant mismatches directly may be optimal. A greedy strategy that always connects nearby mismatches could fail in this situation. The interval DP evaluates all valid pairing structures and therefore correctly chooses long range pairings when they reduce the total cost.

Consecutive Mismatch Positions

When mismatches occur at adjacent indices, the second operation can eliminate them with cost 1. The distance term becomes exactly 1, allowing the DP to recognize and exploit this cheapest possible local fix automatically.