String compression ii

String Dynamic Programming

52.2% acceptance

Feb 25, 2026

2508

221

Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length. Find the minimum length of the run-length encoded version of s after deleting at most k characters.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn get_length_of_optimal_compression(s: String, k: i32) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let k = k as usize;
    const INF: i32 = 1_000_000;
    // dp[i][j] = min encoded length for s[0..i] with j deletions
    let mut dp = vec![vec![INF; k + 1]; n + 1];
    dp[0] = vec![0; k + 1];

    let run_len = |cnt: usize| -> i32 {
      if cnt == 0 { 0 } else if cnt == 1 { 1 }
      else if cnt < 10 { 2 } else if cnt < 100 { 3 } else { 4 }
    };

    for i in 1..=n {
      for j in 0..=k {
        // Option 1: delete s[i-1]
        if j >= 1 {
          dp[i][j] = dp[i][j].min(dp[i-1][j-1]);
        }
        // Option 2: keep s[i-1] in a group [l..i-1]
        let mut same = 0usize;
        let mut diff = 0usize;
        for l in (0..i).rev() {
          if s[l] == s[i-1] { same += 1; } else { diff += 1; }
          if diff > j { break; }
          dp[i][j] = dp[i][j].min(dp[l][j - diff] + run_len(same));
        }
      }
    }

    dp[n][k]
  }
}