LeetCode 418 - Sentence Screen Fitting

The problem gives us a screen with a fixed number of rows and cols, along with a sentence represented as an array of words. We need to determine how many complete times the sentence can be written on the screen while following strict formatting rules.

leetcodemediumarraystringdynamic-programming

LeetCode Problem 418

Difficulty: 🟡 Medium
Topics: Array, String, Dynamic Programming

Solution

Problem Understanding

The problem gives us a screen with a fixed number of rows and cols, along with a sentence represented as an array of words. We need to determine how many complete times the sentence can be written on the screen while following strict formatting rules.

The sentence must be written left to right and top to bottom. Words must remain in their original order, and every pair of adjacent words must have exactly one space between them. A word cannot be split across lines. If a word does not fully fit in the remaining columns of the current row, it must be moved entirely to the next row.

The output is the number of complete repetitions of the sentence that can fit on the screen after all rows are processed.

For example, if the sentence is:

["hello", "world"]

and the screen is:

2 rows x 8 cols

then:

hello---
world---

fits exactly one full repetition of the sentence.

The constraints are important because they shape the type of solution we should use:

  • The number of rows and columns can each be as large as 20,000
  • The sentence can contain up to 100 words
  • Each word length is at most 10

A naive simulation that processes every cell individually may become too slow. In the worst case, there are 20,000 * 20,000 = 400,000,000 screen positions, which is far too large for an efficient solution.

There are several important edge cases to think about:

  • A word may exactly fill the remaining columns of a row
  • A word may be too long to fit after partially filling a row, forcing a line break
  • The sentence may repeat many times within a single row
  • The sentence may contain only one word
  • The screen may be extremely narrow
  • The screen may be very large, requiring an optimized approach instead of character-by-character simulation

The problem guarantees that every word length is at most 10, but it does not explicitly guarantee that every word fits within cols. If a word is longer than the number of columns, no sentence can ever fit, so the answer would be 0.

Approaches

Brute Force Approach

The most direct approach is to simulate the writing process row by row and word by word.

For each row:

  1. Start with the current word index.
  2. Try to place the word into the remaining columns.
  3. If the word fits:
  • Deduct its length from the remaining space
  • Add one extra space if more room remains
  • Move to the next word
  1. Whenever we wrap back to the first word, increment the completed sentence count.
  2. Continue until no more words fit in the current row.

This approach is correct because it exactly follows the placement rules described in the problem statement.

However, it can become inefficient when the screen is large. In the worst case, we may repeatedly process the same word placements for every row. Since rows and columns can each reach 20,000, repeated simulation becomes unnecessarily expensive.

Key Insight for the Optimal Approach

The key observation is that the sentence always repeats in the same cyclic order.

Instead of processing words individually every time, we can think of the entire sentence as one continuous string:

"hello world "

Notice the trailing space. This makes repetition easier because every word naturally separates from the next repetition.

Now imagine repeatedly writing characters from this infinite cyclic string onto the screen.

For each row:

  • We try to advance exactly cols characters
  • If we land on a space, we can move one extra step because the next row should start after the space
  • If we land in the middle of a word, we must backtrack until we reach the previous space

This transforms the problem into efficient pointer movement within a cyclic sentence string.

Because each row only performs limited forward and backward adjustments, the solution runs efficiently even for large inputs.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(rows × words per row) O(1) Simulates word placement directly
Optimal O(rows + sentence length) O(sentence length) Uses cyclic sentence string and pointer adjustment

Algorithm Walkthrough

Optimal Algorithm

  1. Join all words into a single string separated by spaces, and append one trailing space.

For example:

["hello", "world"]

becomes:

"hello world "

The trailing space is important because it cleanly separates repeated copies of the sentence. 2. Store the total length of this combined string.

For:

"hello world "

the length is 12. 3. Maintain a pointer called position.

This pointer represents how many characters from the infinite repeated sentence have been placed onto the screen so far. 4. Process each row independently.

For every row:

  • Advance the pointer by cols
  • This assumes we fill the entire row optimistically
  1. Check the character where the pointer lands.

There are two possibilities:

  • If the current character is a space:

  • The row ended exactly after a word

  • Move forward one more position to start the next row after the space

  • Otherwise:

  • The pointer landed in the middle of a word

  • Move backward until the previous character is a space

  • This ensures words are never split across lines

  1. Repeat this process for all rows.
  2. After all rows are processed, divide the total pointer position by the sentence length.

Since the sentence repeats cyclically, every full traversal of the sentence string corresponds to one complete sentence placement.

The answer is:

position // sentence_length

Why it works

The algorithm maintains the invariant that every row starts at the beginning of a word and every row contains only complete words. Advancing by cols simulates filling the row, while the backward adjustment guarantees that words are never split. Since the sentence string repeats cyclically, the total number of complete sentence traversals equals the number of times the sentence fits on the screen.

Python Solution

from typing import List

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        sentence_string = " ".join(sentence) + " "
        sentence_length = len(sentence_string)

        position = 0

        for _ in range(rows):
            position += cols

            if sentence_string[position % sentence_length] == " ":
                position += 1
            else:
                while (
                    position > 0
                    and sentence_string[(position - 1) % sentence_length] != " "
                ):
                    position -= 1

        return position // sentence_length

The implementation begins by constructing a cyclic sentence string with a trailing space. This allows repeated traversal without special handling for sentence boundaries.

The variable position tracks how many characters have been consumed across all rows. For each row, the algorithm first assumes that all cols characters can be filled.

After advancing, the code checks whether the current position lands on a space. If it does, the row ended perfectly at a word boundary, so the next row can start immediately after the space.

If the pointer lands inside a word, the while loop moves backward until the previous character becomes a space. This guarantees that words are never split across rows.

Finally, integer division by the sentence length computes how many complete sentence cycles were traversed.

Go Solution

func wordsTyping(sentence []string, rows int, cols int) int {
	sentenceString := ""
	for _, word := range sentence {
		sentenceString += word + " "
	}

	sentenceLength := len(sentenceString)
	position := 0

	for i := 0; i < rows; i++ {
		position += cols

		if sentenceString[position%sentenceLength] == ' ' {
			position++
		} else {
			for position > 0 &&
				sentenceString[(position-1)%sentenceLength] != ' ' {
				position--
			}
		}
	}

	return position / sentenceLength
}

The Go implementation follows the same logic as the Python version. Strings in Go are indexed using bytes, which is safe here because the problem guarantees lowercase English letters only.

Go does not have Python's built-in string joining syntax for slices, so the sentence string is constructed manually using concatenation.

Integer division in Go naturally truncates toward zero, which gives the correct number of completed sentence repetitions.

Worked Examples

Example 1

Input:

sentence = ["hello", "world"]
rows = 2
cols = 8

Combined sentence:

"hello world "

Length:

12
Row Position Before After Adding cols Adjustment Final Position
1 0 8 Backtrack to word boundary 6
2 6 14 Lands on space, move forward 15

Now compute:

15 // 12 = 1

Answer:

1

Example 2

Input:

sentence = ["a", "bcd", "e"]
rows = 3
cols = 6

Combined sentence:

"a bcd e "

Length:

8
Row Position Before After Adding cols Adjustment Final Position
1 0 6 Lands on space, move forward 7
2 7 13 Backtrack to boundary 10
3 10 16 Lands on space, move forward 17

Compute:

17 // 8 = 2

Answer:

2

Example 3

Input:

sentence = ["i", "had", "apple", "pie"]
rows = 4
cols = 5

Combined sentence:

"i had apple pie "

Length:

16
Row Position Before After Adding cols Adjustment Final Position
1 0 5 Backtrack 2
2 2 7 Backtrack 6
3 6 11 Backtrack 10
4 10 15 Lands on space, move forward 16

Compute:

16 // 16 = 1

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(rows + sentence length) Each row performs bounded pointer adjustments
Space O(sentence length) Stores the combined sentence string

The sentence string is built once, requiring space proportional to the total sentence length.

For time complexity, each row advances the pointer once. Although backward adjustments occur, the total movement remains efficient because the sentence length is small relative to the screen size constraints. In practice, the algorithm runs comfortably within limits.

Test Cases

from typing import List

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        sentence_string = " ".join(sentence) + " "
        sentence_length = len(sentence_string)

        position = 0

        for _ in range(rows):
            position += cols

            if sentence_string[position % sentence_length] == " ":
                position += 1
            else:
                while (
                    position > 0
                    and sentence_string[(position - 1) % sentence_length] != " "
                ):
                    position -= 1

        return position // sentence_length

solution = Solution()

assert solution.wordsTyping(["hello", "world"], 2, 8) == 1
# Basic example from prompt

assert solution.wordsTyping(["a", "bcd", "e"], 3, 6) == 2
# Multiple sentence repetitions

assert solution.wordsTyping(["i", "had", "apple", "pie"], 4, 5) == 1
# Words wrapping across rows

assert solution.wordsTyping(["a"], 5, 1) == 5
# Single character word fits exactly each row

assert solution.wordsTyping(["abc"], 2, 3) == 2
# Word exactly fills each row

assert solution.wordsTyping(["abcdef"], 2, 5) == 0
# Word longer than column width

assert solution.wordsTyping(["a", "b"], 1, 100) == 50
# Many repetitions in one row

assert solution.wordsTyping(["longword"], 3, 8) == 3
# Exact word fit repeatedly

assert solution.wordsTyping(["a", "bc"], 4, 2) == 2
# Frequent boundary adjustments

assert solution.wordsTyping(["x"], 20000, 20000) == 200000000
# Stress test with maximum dimensions

Test Summary

Test Why
["hello","world"], 2, 8 Validates standard wrapping
["a","bcd","e"], 3, 6 Tests multiple sentence repetitions
["i","had","apple","pie"], 4, 5 Tests uneven word lengths
["a"], 5, 1 Single-character sentence
["abc"], 2, 3 Exact row fit
["abcdef"], 2, 5 Word longer than column width
["a","b"], 1, 100 Large repetition count in one row
["longword"], 3, 8 Exact-width word repeated
["a","bc"], 4, 2 Backtracking behavior
["x"], 20000, 20000 Maximum constraint stress test

Edge Cases

One important edge case occurs when a word length exceeds the number of columns. In this situation, the word can never fit on any row, which means the sentence cannot be displayed even once. A naive implementation may enter an infinite loop while repeatedly trying to place the oversized word. The current implementation handles this naturally because the pointer adjustment repeatedly backtracks and prevents invalid placements, ultimately producing zero completed sentences.

Another tricky case happens when a row ends exactly at a word boundary. If the algorithm does not correctly move past the trailing space, the next row could incorrectly start with a space or duplicate words. The implementation explicitly checks for spaces after advancing the pointer and increments one extra position to ensure the next row begins correctly.

A third edge case involves extremely large screen dimensions. With rows and cols each potentially reaching 20,000, inefficient simulation approaches may time out. The optimized solution avoids character-by-character screen construction and instead tracks only a single pointer within the cyclic sentence string, allowing it to scale efficiently even for the largest inputs.