Sentence screen fitting

Array String Dynamic Programming

36.4% acceptance

Mar 31, 2026

1143

543

No description available.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn words_typing(sentence: Vec<String>, rows: i32, cols: i32) -> i32 {
    // Build the sentence string with a trailing space
    let joined: String = sentence.join(" ") + " ";
    let m = joined.len();
    let cols = cols as usize;

    // Precompute: for each starting position in joined,
    // how many characters we advance in one row
    let bytes = joined.as_bytes();
    let mut advance = vec![0usize; m];
    for i in 0..m {
      let mut count = cols;
      let pos = (i + count) % m;
      // If we land on a space, move forward; if on non-space, backtrack to space
      // Actually simulate: fill cols characters, then skip to next word start
      let end = i + count;
      let idx = end % m;
      if bytes[idx] == b' ' {
        // We ended exactly on a space boundary, advance past it
        advance[i] = count + 1;
      } else {
        // Backtrack to the last space
        // Find last space <= end - 1 in the circular buffer from i
        let mut back = end;
        while back > i && bytes[back % m] != b' ' {
          back -= 1;
        }
        // If we backtracked all the way to i and it's not a space,
        // no word fits on this row — make no progress.
        if back == i && bytes[i % m] != b' ' {
          advance[i] = 0;
        } else {
          advance[i] = back - i + 1;
        }
      }
    }

    let mut start = 0usize;
    let mut total = 0usize;
    for _ in 0..rows as usize {
      total += advance[start];
      start = (start + advance[start]) % m;
    }

    (total / m) as i32
  }
}