Watch 10 video solutions for Sentence Screen Fitting, a medium level problem involving Array, String, Dynamic Programming. This walkthrough by NeetCode has 611,557 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= sentence[i].length <= 10sentence[i] consists of lowercase English letters.1 <= rows, cols <= 2 * 104Problem Overview: You get a screen with rows and cols. A sentence (array of words) must be written left to right with single spaces between words. Words cannot be split across lines. The task is to compute how many complete times the sentence fits on the screen.
Approach 1: Row Simulation (Brute Force) (Time: O(rows * words), Space: O(1))
Simulate filling the screen row by row. Maintain an index pointing to the current word in the sentence. For each row, repeatedly place words while the total length plus required spaces stays within cols. Move the pointer to the next word and wrap around to the beginning when the sentence ends. Each wrap means one full sentence was printed. This approach is straightforward and mirrors the real placement process, but it repeatedly checks word lengths for every row which can be slow when rows is large. The logic mainly relies on iterating through the sentence array and tracking remaining column space.
Approach 2: Greedy String Cycling (Optimal) (Time: O(rows), Space: O(n))
Concatenate the entire sentence into a single string s with spaces and add a trailing space: "word1 word2 ... ". Track a pointer representing how many characters have been placed on the screen so far. For each row, advance the pointer by cols. If the next character is a space, move one more step since a word boundary aligns perfectly. If it lands in the middle of a word, move the pointer backward until the previous space appears. This guarantees words never split across lines. After processing all rows, divide the pointer by the length of s to determine how many full repetitions of the sentence fit. The key insight is treating the sentence as a cyclic string rather than repeatedly scanning the word list.
This method leverages properties of string traversal and avoids per-word checks. It effectively compresses the placement process into pointer arithmetic while respecting word boundaries.
Recommended for interviews: The greedy string cycling approach is the expected solution. It reduces repeated scanning and handles each row in constant work, giving O(rows) time. Interviewers often look for the insight that the sentence can be treated as a repeating string. The brute-force simulation demonstrates understanding of the placement rules, but the optimized solution shows stronger mastery of array iteration patterns and dynamic programming-style reuse of structure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Row-by-Row Simulation | O(rows * words) | O(1) | Good for understanding the placement rules or when rows are small |
| Greedy String Cycling | O(rows) | O(n) | Optimal approach for large screens; avoids repeated word scans |