Minimum cost good caption

String Dynamic Programming

20.6% acceptance

Feb 25, 2026

You are given a string caption of length n. A good caption is a string where every character appears in groups of at least 3 consecutive occurrences. For example: "aaabbb" and "aaaaccc" are good captions. "aabbb" and "ccccd" are not good captions. You can perform the following operation any number of times: Choose an index i (where 0 <= i < n) and change the character at that index to either: The character immediately before it in the alphabet (if caption[i] != 'a'). The character immediately after it in the alphabet (if caption[i] != 'z'). Your task is to convert the given caption into a good caption using the minimum number of operations, and return it. If there are multiple possible good captions, return the lexicographically smallest one among them. If it is impossible to create a good caption, return an empty string "".

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost_good_caption(caption: String) -> String {
    let n = caption.len();
    if n < 3 { return String::new(); }
    let s: Vec<i64> = caption.bytes().map(|b| (b - b'a') as i64).collect();
    const INF: i64 = i64::MAX / 2;

    // prefix[i][c] = sum_{j<i} |s[j] - c|
    let mut prefix = vec![[0i64; 26]; n + 1];
    for j in 0..n {
      for c in 0..26usize {
        prefix[j + 1][c] = prefix[j][c] + (s[j] - c as i64).abs();
      }
    }
    // cost(i, j, c) = prefix[j][c] - prefix[i][c]

    // dp_bwd[i] = min cost to make s[i..n] a valid good caption.
    // dp_bwd[i] = min_c (-prefix[i][c] + sf_min[c])
    // where sf_min[c] = min_{j >= i+3} (prefix[j][c] + dp_bwd[j])
    // Compute by iterating i from n-3 down to 0, adding j=i+3 into sf_min at each step.
    let mut dp_bwd = vec![INF; n + 1];
    dp_bwd[n] = 0;
    // sf_min[c] = running suffix min of (prefix[j][c] + dp_bwd[j]) for j in [i+3..=n]
    let mut sf_min = [INF; 26];

    for i in (0..=(n - 3)).rev() {
      // Add j = i+3 to sf_min
      let j = i + 3;
      if dp_bwd[j] < INF {
        for c in 0..26usize {
          let val = prefix[j][c] + dp_bwd[j];
          if val < sf_min[c] { sf_min[c] = val; }
        }
      }
      // Compute dp_bwd[i]
      for c in 0..26usize {
        if sf_min[c] < INF {
          let val = sf_min[c] - prefix[i][c];
          if val < dp_bwd[i] { dp_bwd[i] = val; }
        }
      }
    }

    if dp_bwd[0] == INF { return String::new(); }

    // Compute best_char[i] = lex-smallest starting character for optimal solution from i
    let mut best_char = vec![26usize; n + 1];
    let mut sf_min2 = [INF; 26];
    for i in (0..=(n - 3)).rev() {
      let j = i + 3;
      if dp_bwd[j] < INF {
        for c in 0..26usize {
          let val = prefix[j][c] + dp_bwd[j];
          if val < sf_min2[c] { sf_min2[c] = val; }
        }
      }
      for c in 0..26usize {
        if sf_min2[c] < INF {
          let val = sf_min2[c] - prefix[i][c];
          if val == dp_bwd[i] && c < best_char[i] {
            best_char[i] = c;
          }
        }
      }
    }

    // Greedy reconstruction: at each pos, use best_char[pos] = c.
    // Among j >= pos+3 achieving the min cost, pick smallest j where best_char[j] < c
    // (end the block early to get a lex-smaller next char), else pick the largest j.
    let mut result = vec![0u8; n];
    let mut pos = 0;
    while pos < n {
      let c = best_char[pos];
      let target = dp_bwd[pos] + prefix[pos][c];
      let mut last_valid_j = pos + 3;
      let mut chosen_j = n + 1; // sentinel

      for j in (pos + 3)..=n {
        if dp_bwd[j] == INF { continue; }
        if prefix[j][c] + dp_bwd[j] == target {
          last_valid_j = j;
          if j == n || best_char[j] < c {
            chosen_j = j;
            break;
          }
        }
      }
      if chosen_j == n + 1 { chosen_j = last_valid_j; }

      for k in pos..chosen_j { result[k] = b'a' + c as u8; }
      pos = chosen_j;
    }

    String::from_utf8(result).unwrap()
  }
}