Minimum steps to convert string with operations

String Dynamic Programming Greedy

42.8% acceptance

Feb 25, 2026

Transform word1 into word2 by dividing into substrings, applying replace/swap/reverse ops. Each index can be used in at most one replace, one swap, one reverse per substring. Return minimum total operations.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(word1: String, word2: String) -> i32 {
    let n = word1.len();
    let b1 = word1.as_bytes();
    let b2 = word2.as_bytes();

    // For a substring [i..j], compute minimum ops to transform b1[i..=j] to b2[i..=j].
    // Operations per char in substring: replace (1 per char changed), swap (1 for a pair exchange),
    // reverse (1 for the whole substring).
    // Key: for a segment of length L:
    //   - reverse costs 1 operation total
    //   - swap costs 1 per pair swapped
    //   - replace costs 1 per character replaced
    //   So minimum cost to transform s1 to s2 within a segment is:
    //     Let mismatches = positions where s1[k] != s2[k].
    //     If we can reverse s1 and match: count mismatches after reverse. Cost = 1 + matches_after_rev.
    //     Pairs that match up via swap: pairs (k, l) where s1[k]=s2[l] and s1[l]=s2[k] cost 1 swap.
    //     Remaining mismatches cost 1 replace each.
    //   Optimal for direct (no reverse): mismatches - 2*swap_pairs + swap_pairs = mismatches - swap_pairs
    //     where swap_pairs = # pairs (k<l) with s1[k]=s2[l] and s1[l]=s2[k].
    //   Optimal with reverse: reverse, then count remaining mismatches similarly.

    // For the segment [i..=j], compute cost (no reverse) and (with reverse):
    // cost_no_rev = mismatches - swap_pairs
    // cost_with_rev = 1 + mismatches_after_rev - swap_pairs_after_rev (minimum of applying reverse first)

    // cost[i][j] for segment [i..=j]
    let cost = |i: usize, j: usize| -> i32 {
      let s1 = &b1[i..=j];
      let s2 = &b2[i..=j];
      let l = j - i + 1;

      let direct_cost = |s1: &[u8], s2: &[u8]| -> i32 {
        // Count mismatches, then count swap pairs
        let mut diff_positions: Vec<usize> = vec![];
        for k in 0..l {
          if s1[k] != s2[k] {
            diff_positions.push(k);
          }
        }
        let nd = diff_positions.len();
        // Count swap pairs: pairs (a, b) in diff_positions where s1[a]=s2[b] and s1[b]=s2[a]
        let mut used = vec![false; nd];
        let mut swaps = 0i32;
        for a in 0..nd {
          if used[a] { continue; }
          for b in a + 1..nd {
            if used[b] { continue; }
            let pa = diff_positions[a];
            let pb = diff_positions[b];
            if s1[pa] == s2[pb] && s1[pb] == s2[pa] {
              swaps += 1;
              used[a] = true;
              used[b] = true;
              break;
            }
          }
        }
        // Remaining mismatches = nd - 2*swaps; each costs replace(1)
        // swap cost = swaps * 1
        // total = swaps + (nd - 2*swaps) = nd - swaps
        nd as i32 - swaps
      };

      let c1 = direct_cost(s1, s2);
      // With reverse: s1_rev -> try to match s2
      let s1_rev: Vec<u8> = s1.iter().cloned().rev().collect();
      let c2 = 1 + direct_cost(&s1_rev, s2);
      c1.min(c2)
    };

    // DP: dp[i] = min ops to convert word1[0..i-1] to word2[0..i-1]
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in 1..=n {
      for j in 0..i {
        if dp[j] == i32::MAX { continue; }
        let c = cost(j, i - 1);
        if dp[j] + c < dp[i] {
          dp[i] = dp[j] + c;
        }
      }
    }
    dp[n]
  }
}