Skip to main content
Talentd

Sentence Screen Fitting - Solution & Explanation

MediumPremiumFree on FleetCodeArrayStringDynamic Programming5 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

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

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Row-by-Row SimulationO(rows * words)O(1)Good for understanding the placement rules or when rows are small
Greedy String CyclingO(rows)O(n)Optimal approach for large screens; avoids repeated word scans

Video Solution

Google Coding Interview Question | Leetcode 418 | Sentence Screen Fitting • WorkWithGoogler • 8,063 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Sentence Screen Fitting with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Separate Sentence Into Rows

Next

Split Message Based on Limit