Strange printer

String Dynamic Programming

60.9% acceptance

Feb 20, 2026

2768

289

Strange printer: You have a printer that can print a sequence of the same character each time and covers any existing characters. Return the minimum number of turns to print string s.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn strange_printer(s: String) -> i32 {
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n { dp[i][i] = 1; }
    for len in 2..=n {
      for i in 0..=n - len {
        let j = i + len - 1;
        dp[i][j] = dp[i][j - 1] + 1;
        for k in i..j {
          if s[k] == s[j] {
            let val = dp[i][k] + if k + 1 <= j - 1 { dp[k + 1][j - 1] } else { 0 };
            if val < dp[i][j] {
              dp[i][j] = val;
            }
          }
        }
      }
    }
    dp[0][n - 1]
  }
}