# Sentence Screen Fitting

Published: Jan 25, 2023

Medium Dynamic Programming String

## Problem Description

Given a `rows x cols` screen and a `sentence` represented as a list of strings, return the number of times the given sentence can be fitted on the screen.

The order of words in the sentence must remain unchanged, and a word cannot be split into two lines. A single space must separate two consecutive words in a line.

Constraints: `-1 <= sentence.length <= 100`

• `1 <= sentence[i].length <= 10`
• `sentence[i]` consists of lowercase English letters.
• `1 <= rows, cols <= 2 * 10**4`

https://leetcode.com/problems/sentence-screen-fitting/

## Examples

``````Example 1
Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1
Explanation:
hello___
world___
``````
``````Example 2
Input: sentence = ["a", "bcd", "e"], rows = 3, cols = 6
Output: 2
Explanation:
a_bcd_
e_a___
bcd_e_
``````
``````Example 3
Input: sentence = ["i","had","apple","pie"], rows = 4, cols = 5
Output: 1
Explanation:
apple
pie_i
``````

## How to Solve

The memoization (dynamic programming) is a good approach for this problem. The auxiliary array saves the each character position and word end marker of -1. Once auxiliary array is created, count how many entire sentence fit in a single row. The count goes up to the end of rows * cols, so the answer should be divided by the sentence length.

## Solution

``````class SentenceScreenFitting {
public:
int wordsTyping(vector<string>& sentence, int rows, int cols) {
string words = "";
for (string &word : sentence) {
words += word + ' ';
}
int start = -1, n = words.size();
vector<int> memo(n, 0);
for (int i = 0; i < n; ++i) {
if (words[i] == ' ') {
start = i;
}
memo[i] = i - start - 1;
}
int length = 0;
for (int r = 0; r < rows; ++r) {
length += cols;
length -= memo[length % n];
}
return (length + 1) / n;
}
};
``````
``````
``````
``````
``````
``````class SentenceScreenFitting:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
words = ' '.join(sentence) + ' '
start, n = -1, len(words)
memo = [0 for _ in range(n)]
for i in range(n):
if words[i] == ' ':
start = i
memo[i] = i - start - 1
length = 0
for _ in range(rows):
length += cols
length -= memo[length % n]
return (length + 1) // n
``````
``````
``````

## Complexities

• Time: `O(n)` – n: number of rows. A sentence and each word have upper bound of 100 and 10 respectively. Those are constant
• Space: `O(1)`