Skip to main content
Back to problems
#2052
Medium Algorithms

Minimum cost to separate sentence into rows

String Dynamic Programming
51.2% acceptance
Mar 31, 2026
45
14

No description available.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn minimum_cost(sentence: String, k: i32) -> i32 {
    let words: Vec<&str> = sentence.split(' ').collect();
    let n = words.len();
    let k = k as usize;
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;

    for i in 1..=n {
      let mut len = 0usize;
      for j in (1..=i).rev() {
        len += words[j - 1].len();
        if j < i {
          len += 1; // space
        }
        if len > k {
          break;
        }
        if dp[j - 1] == i32::MAX {
          continue;
        }
        if i == n {
          // last row: cost is 0
          dp[i] = dp[i].min(dp[j - 1]);
        } else {
          let cost = (k - len) * (k - len);
          dp[i] = dp[i].min(dp[j - 1] + cost as i32);
        }
      }
    }

    dp[n]
  }
}