Encode string with shortest length

String Dynamic Programming

50.6% acceptance

Mar 31, 2026

632

Given a string s, encode the string such that its encoded length is the shortest. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. k should be a positive integer. If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn encode(s: String) -> String {
    let n = s.len();
    let mut dp = vec![vec![String::new(); n]; n];
    
    for len in 1..=n {
      for i in 0..=n - len {
        let j = i + len - 1;
        let sub = &s[i..=j];
        dp[i][j] = sub.to_string();
        
        if len <= 4 {
          continue;
        }
        
        // Try splitting into two parts
        for k in i..j {
          let combined_len = dp[i][k].len() + dp[k + 1][j].len();
          if combined_len < dp[i][j].len() {
            dp[i][j] = format!("{}{}", dp[i][k], dp[k + 1][j]);
          }
        }
        
        // Try encoding as k[pattern] using KMP trick
        let doubled = format!("{}{}", sub, sub);
        if let Some(pos) = doubled[1..].find(sub) {
          let period = pos + 1;
          if len % period == 0 {
            let count = len / period;
            let encoded_pattern = &dp[i][i + period - 1];
            let candidate = format!("{}[{}]", count, encoded_pattern);
            if candidate.len() < dp[i][j].len() {
              dp[i][j] = candidate;
            }
          }
        }
      }
    }
    
    dp[0][n - 1].clone()
  }
}