Decremental string concatenation

Array String Dynamic Programming

27.4% acceptance

Feb 25, 2026

375

You are given a 0-indexed array words containing n strings. Let's define a join operation join(x, y) between two strings x and y as concatenating them into xy. However, if the last character of x is equal to the first character of y, one of them is deleted. For example join("ab", "ba") = "aba" and join("ab", "cde") = "abcde". You are to perform n - 1 join operations. Let str0 = words[0]. Starting from i = 1 up to i = n - 1, for the ith operation, you can do one of the following: Make stri = join(stri - 1, words[i]) Make stri = join(words[i], stri - 1) Your task is to minimize the length of strn - 1. Return an integer denoting the minimum possible length of strn - 1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimize_concatenated_length(words: Vec<String>) -> i32 {
    use std::collections::HashMap;
    // dp[(first_char, last_char)] = minimum length
    let mut dp: HashMap<(u8, u8), i32> = HashMap::new();
    let w0 = words[0].as_bytes();
    let (f0, l0) = (w0[0], w0[w0.len() - 1]);
    dp.insert((f0, l0), w0.len() as i32);

    for i in 1..words.len() {
      let wi = words[i].as_bytes();
      let (wf, wl) = (wi[0], wi[wi.len() - 1]);
      let wlen = wi.len() as i32;
      let mut new_dp: HashMap<(u8, u8), i32> = HashMap::new();
      for (key, &len) in &dp {
        let (f, l) = *key;
        // Append words[i]: join(current, words[i])
        let add1 = if l == wf { wlen - 1 } else { wlen };
        let e1 = new_dp.entry((f, wl)).or_insert(i32::MAX);
        *e1 = (*e1).min(len + add1);
        // Prepend words[i]: join(words[i], current)
        let add2 = if wl == f { wlen - 1 } else { wlen };
        let e2 = new_dp.entry((wf, l)).or_insert(i32::MAX);
        *e2 = (*e2).min(len + add2);
      }
      dp = new_dp;
    }
    *dp.values().min().unwrap()
  }
}