Is Sentence Screen Fitting easy or hard?

Sentence Screen Fitting is considered a medium difficulty problem. The brute-force simulation is easy to implement, but recognizing the cyclic string optimization requires stronger algorithmic insight.

Sentence Screen Fitting Python/Java solution

Python and Java implementations typically follow the greedy string cycling technique. Build the sentence string with spaces, track a pointer that increases by the column width each row, and adjust to the previous space if necessary. The final answer is pointer divided by the sentence length.

How to solve Sentence Screen Fitting in O(n)?

Build a single string containing the entire sentence with spaces and a trailing space. Maintain a pointer representing the number of characters placed on the screen. For each row add the column width, then adjust the pointer to the nearest valid space boundary if it lands inside a word. The total pointer movement divided by the sentence string length gives the number of complete fits.

What is the best approach for Sentence Screen Fitting?

The most efficient approach treats the sentence as a cyclic string. Concatenate the words with spaces and simulate placing characters row by row using a pointer. Each row advances by the column width, then adjusts to the nearest space boundary. This runs in O(rows) time and avoids repeatedly scanning individual words.

Is Sentence Screen Fitting asked at Google/Amazon/Meta?

Sentence Screen Fitting has appeared in interviews at companies like Google and other large tech firms because it tests string manipulation and optimization thinking. Candidates must recognize the repeating pattern in the sentence rather than simulate word placement naively.

What data structure is used in Sentence Screen Fitting?

The problem mainly relies on strings and arrays. The optimal solution converts the array of words into a single string and uses pointer arithmetic to simulate screen placement. No complex structures like heaps or trees are required.

What is the time complexity of Sentence Screen Fitting?

The optimized greedy solution runs in O(rows) time because each row performs constant work. Space complexity is O(n) where n is the length of the concatenated sentence string. A simpler brute-force simulation may take O(rows * words) time because it checks each word placement repeatedly.

Description Solution Video 15:31

418. Sentence Screen Fitting

Medium36.3% acceptance1 companyPremium elsewhere, free here

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: