Skip to content
MediumDpAI interview only

Apply Operations to Make Two Strings Equal

Asked atgoogleamazonmicrosoft

01 · Problem

You are given two binary strings s1 and s2 of the same length n, and a positive integer x. You may apply the following operations to s1 any number of times, in any order:

  • Pick any two indices i and j (i != j, not necessarily adjacent) and flip both s1[i] and s1[j]. This costs x.
  • Pick an index i with i + 1 < n and flip both s1[i] and s1[i + 1]. This costs 1.

Flipping a character turns '0' into '1' and vice versa. Return the minimum total cost to make s1 identical to s2, or -1 if it cannot be done. If the strings are already equal, return 0.

02 · Examples

Example 01
Input
s1 = "10110", s2 = "01101", x = 3
Output
2

The strings differ at indices 0, 1, 3 and 4. Flip the adjacent pair (0, 1) for cost 1 and the adjacent pair (3, 4) for cost 1, for a total of 2.

Example 02
Input
s1 = "1001", s2 = "0000", x = 5
Output
3

Indices 0 and 3 must change. Flipping them together costs 5, but flipping (0, 1), then (1, 2), then (2, 3) costs only 3: index 1 and index 2 are each flipped twice and end unchanged.

Example 03
Input
s1 = "100", s2 = "000", x = 2
Output
-1

Every operation flips exactly two characters, so the number of mismatched positions keeps its parity. One mismatch can never be fixed.

03 · Constraints

  • 01n == s1.length == s2.length
  • 021 <= n <= 500
  • 031 <= x <= 500
  • 04s1[i] and s2[i] are either '0' or '1'

04 · Optimal complexity

Time
O(n)
Space
O(n)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem