Sentence Screen Fitting

Sentence Screen Fitting

What is this problem about?

The Sentence Screen Fitting interview question gives you a list of words forming a sentence and a screen of rows × cols dimensions. Determine how many times the entire sentence can be displayed on the screen, starting from the top-left, wrapping to the next row when a word doesn't fit (you cannot split a word). Words within a row are separated by a single space. This is a simulation with dynamic programming optimization.

Why is this asked in interviews?

Google asks this MEDIUM problem because it tests simulation combined with memoization. The naive simulation is O(rows × len(sentence)) which can be slow for large inputs. The optimized approach observes that each row begins at a fixed position within the sentence — there are at most len(sentence) distinct starting positions, so rows cycle. Memoizing the advance (next start index and complete-sentence count per starting word) reduces it to O(len(sentence) × cols) preprocessing followed by O(rows) simulation.

Algorithmic pattern used

The pattern is simulation with memoization on sentence position. For each starting word index start, simulate filling one row of cols characters: greedily add words with spaces. Track how many full sentence wraps occur and what the next starting word index is. Cache (next_start, wraps_count) for each starting word. Then simulate all rows, using the cache to skip repeated work. The total count is the sum of all wrap counts across rows.

Example explanation

Words: ["I", "had", "apple", "pie"], rows=4, cols=5.

Row 1: starts at word 0 ("I"). Fits: "I had" (5 chars) → next row starts at word 2. Wrap count=0. Row 2: starts at word 2 ("apple"). Fits: "apple" (5 chars) → next at word 3. Wraps=0. Row 3: starts at word 3 ("pie"). Fits: "pie" then wraps to "I" on next → next at word 1, wraps+=1. Row 4: starts at word 1 ("had"). Fits: "had" → wraps to "apple" next... and so on.

Total complete sentences across 4 rows: 1.

Common mistakes candidates make

• Splitting words mid-row — words cannot be broken; if a word doesn't fit with its preceding space, move it entirely to the next row.
• Not handling the sentence wrap-around correctly — after the last word, the next word is the first word again.
• Simulating each character individually instead of word-by-word — very slow for long rows.
• Not memoizing: without caching on the start-word position, the simulation repeats cycles for large row counts.

Interview preparation tip

For the Sentence Screen Fitting coding problem, the dynamic programming string interview pattern with cycle detection is the efficient approach. Google interviewers reward candidates who identify the cycling behavior — once you've seen a starting word position before, the pattern repeats. Practice the "simulate one step, memoize by state" pattern — it generalizes to scrolling text display problems, word wrap algorithms, and text editor layout engines.