Equalize strings by adding or removing characters at ends

String Binary Search Dynamic Programming Sliding Window Hash Function

56.1% acceptance

Mar 31, 2026

Given two strings initial and target, your task is to modify initial by performing a series of operations to make it equal to target. In one operation, you can add or remove one character only at the beginning or the end of the string initial. Return the minimum number of operations required to transform initial into target.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(initial: String, target: String) -> i32 {
    let a = initial.as_bytes();
    let b = target.as_bytes();
    let n = a.len();
    let m = b.len();
    let mut max_len = 0;
    let mut dp = vec![vec![0u16; m + 1]; n + 1];
    for i in 1..=n {
      for j in 1..=m {
        if a[i - 1] == b[j - 1] {
          dp[i][j] = dp[i - 1][j - 1] + 1;
          if dp[i][j] as usize > max_len {
            max_len = dp[i][j] as usize;
          }
        }
      }
    }
    (n + m - 2 * max_len) as i32
  }
}