# 0418. Sentence Screen Fitting

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

## 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.

**Example 1:**

```
**Input:** sentence = ["hello","world"], rows = 2, cols = 8
**Output:** 1
**Explanation:**
hello---
world---
The character '-' signifies an empty space on the screen.
```

**Example 2:**

```
**Input:** sentence = ["a", "bcd", "e"], rows = 3, cols = 6
**Output:** 2
**Explanation:**
a-bcd- 
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.
```

**Example 3:**

```
**Input:** sentence = ["i","had","apple","pie"], rows = 4, cols = 5
**Output:** 1
**Explanation:**
i-had
apple
pie-i
had--
The character '-' signifies an empty space on the screen.
```

**Constraints:**

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

## ac1: brute force

TLE

```java
class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        // edge cases
        if (sentence == null || sentence.length == 0 || rows <= 0 || cols <= 0) 
            return 0;

        int n = sentence.length;
        int s = 0;  // sentence index
        for (int r = 0, c = 0; r < rows; r++) {
            if (sentence[s%n].length() > cols) return 0;  // one word is longer than screen

            while (cols - c >= sentence[s%n].length()) {  // remaining space can fit next word
                c += sentence[s%n].length() + 1;
                s++;
            } 

            c = 0;  // new row, restart
        }

        return s / n;
    }
}
```

## ac2: memorization

```java
class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        // edge cases
        if (sentence == null || sentence.length == 0 || rows <= 0 || cols <= 0) 
            return 0;

        int n = sentence.length;
        int[] times = new int[n];
        int[] nextIdx = new int[n];

        for (int i = 0; i < n; i++) {
            int c = 0;  // current column
            int curr = i;  // sentence index
            int time = 0;  // does this line finish one round?
            while (c + sentence[curr].length() <= cols) {  // remaining space can put current word
                c += sentence[curr++].length() + 1;  // one space after, so + 1
                if (curr == n) {  // finish one round, reset to beginning
                    time++;
                    curr = 0;
                }
            }

            nextIdx[i] = curr;  // the begin index for next line
            times[i] = time;
        }

        int res = 0;
        int s = 0;  // index of sentence
        for (int i = 0; i < rows; i++) {
            res += times[s];
            s = nextIdx[s];
        }

        return res;
    }
}

/*
memorization, if row start with sentence[s], what is the times and starting index for next line.
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0418-sentence-screen-fitting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.