Apply operations to make two strings equal

String Dynamic Programming

27.6% acceptance

Feb 25, 2026

393

You are given two 0-indexed binary strings s1 and s2, both of length n, and a positive integer x. You can perform any of the following operations on the string s1 any number of times: Choose two indices i and j, and flip both s1[i] and s1[j]. The cost of this operation is x. Choose an index i such that i < n - 1 and flip both s1[i] and s1[i + 1]. The cost of this operation is 1. Return the minimum cost needed to make the strings s1 and s2 equal, or return -1 if it is impossible. Note that flipping a character means changing it from 0 to 1 or vice-versa.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(s1: String, s2: String, x: i32) -> i32 {
    let n = s1.len();
    let b1: Vec<u8> = s1.bytes().collect();
    let b2: Vec<u8> = s2.bytes().collect();
    // Positions where s1 and s2 differ
    let diff: Vec<usize> = (0..n).filter(|&i| b1[i] != b2[i]).collect();
    if diff.len() % 2 != 0 { return -1; }
    if diff.is_empty() { return 0; }
    let m = diff.len();
    let x = x as i64;
    // Interval DP: dp[i][j] = min cost to pair all diffs in diff[i..=j] (j-i+1 must be even)
    // Pair diff[i] with diff[k], then independently solve diff[i+1..=k-1] and diff[k+1..=j]
    let mut dp = vec![vec![i64::MAX / 2; m]; m];
    // Base case: pairs of 2
    for i in 0..m - 1 {
      dp[i][i + 1] = ((diff[i + 1] - diff[i]) as i64).min(x);
    }
    // Fill larger intervals (step by 2 since count must be even)
    let mut len = 4usize;
    while len <= m {
      let mut i = 0usize;
      while i + len - 1 < m {
        let j = i + len - 1;
        dp[i][j] = i64::MAX / 2;
        // Pair diff[i] with diff[k] for k = i+1, i+3, ..., j
        let mut k = i + 1;
        while k <= j {
          let pair_cost = ((diff[k] - diff[i]) as i64).min(x);
          let inner = if k > i + 1 { dp[i + 1][k - 1] } else { 0 };
          let outer = if k < j { dp[k + 1][j] } else { 0 };
          let total = pair_cost + inner + outer;
          if total < dp[i][j] { dp[i][j] = total; }
          k += 2;
        }
        i += 1;
      }
      len += 2;
    }
    dp[0][m - 1] as i32
  }
}