LeetCode 418: Sentence Screen Fitting Solution in Python – A Step-by-Step Guide

What Is LeetCode 418: Sentence Screen Fitting?

In LeetCode 418: Sentence Screen Fitting, you’re given three inputs: rows (number of screen rows), cols (number of columns per row), and sentence (a list of words, e.g., ["a", "b", "c"]). Your task is to return how many times the sentence (joined with spaces, e.g., "a b c") can fully fit on the screen as it scrolls left to right. Words can’t be split across lines, and each row must fit whole words followed by spaces. For a 4×6 screen with ["a", "b", "c"], the sentence "a b c" (5 chars with spaces) fits twice, with some leftover space. The output is the count of complete sentence fits.

Problem Statement

• Input: rows (int), cols (int), sentence (list of strings).
• Output: An integer—number of times sentence fits on the screen.
• Rules:
• Sentence is joined with spaces (e.g., "a b c").
• Words can’t split across rows.
• Each row fits whole words plus spaces, up to cols.

Constraints

• 1 <= sentence.length <= 100.
• 1 <= sentence[i].length <= 10.
• 1 <= rows, cols <= 20,000.

Examples

• Input: rows = 2, cols = 8, sentence = ["hello","world"]
• Output: 1 ("hello world" fits once, 11 chars > 8, next row fits "hello").
• Input: rows = 3, cols = 6, sentence = ["a","b","c"]
• Output: 2 ("a b c" fits twice, 5 chars per row).
• Input: rows = 4, cols = 5, sentence = ["I","had"]
• Output: 1 ("I had" fits once, 6 chars > 5).

Understanding the Problem: Fitting the Sentence

To solve LeetCode 418: Sentence Screen Fitting in Python, we need to count how many times sentence (joined with spaces) fits into a rows × cols screen, ensuring words stay whole and fit within column limits. A naive idea might be to simulate every row—but with up to 20,000 rows, that’s too slow for big cases! Instead, we’ll use:

• Best Solution (Optimized Iteration with Pointer Adjustment): O(rows + n) time, O(1) space—leverages sentence repetition.
• Alternative Solution (Brute Force Simulation): O(rows * cols) time, O(1) space—simulates character-by-character.

Let’s dive into the optimized solution with a clear, step-by-step explanation.

Best Solution: Optimized Iteration with Pointer Adjustment

Why This Is the Best Solution

The optimized iteration with pointer adjustment method is the top pick because it’s fast—O(rows + n) time, O(1) space—and cleverly uses the sentence’s repeating pattern to skip redundant work. It tracks a pointer in the sentence string, adjusts it row-by-row based on column fits, and counts full repetitions without simulating every character. It’s like fast-forwarding through a looping ticker tape to tally complete plays!

How It Works

Think of the sentence as a scrolling marquee:

• Step 1: Prepare the Sentence:
• Join sentence with spaces (e.g., "a b c"), length = n.
• Step 2: Initialize Tracking:
• start: Pointer to current position in sentence (starts at 0).
• count: Number of full sentence fits (starts at 0).
• Step 3: Process Each Row:
• For each row:
• Fit as many characters as cols allow from start.
• If hit a space or end, move start forward by cols.
• If hit a letter, rewind start to last space (no split).
• Increment count when start wraps past sentence length.
• Update start modulo sentence length.
• Step 4: Why This Works:
• Sentence repeats cyclically, so pointer wraps naturally.
• Adjusting for spaces ensures whole words.
• Counts full fits without full simulation.

Step-by-Step Example

Example: rows = 3, cols = 6, sentence = ["a","b","c"]

• Sentence: "a b c", length = 5.
• Start: start = 0, count = 0.
• Row 1:
• From 0: "a b c" (5 ≤ 6), fits, start += 6 = 6.
• 6 % 5 = 1, count += 6 // 5 = 1 (one full fit).
• Row 2:
• From 1: "b c" (3) + " " + "a" (1) = 5 ≤ 6, start += 6 = 7.
• 7 % 5 = 2, count += 6 // 5 = 2.
• Row 3:
• From 2: "c" (1) + " " + "a b" (3) = 5 ≤ 6, start += 6 = 8.
• 8 % 5 = 3, count += 6 // 5 = 3.
• Result: count = 2 (two full fits), return 2.

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

• Sentence: "hello world", length = 11.
• Row 1: From 0: "hello" (5) + " " (6) ≤ 8, rewind to 0 (no split), start += 8 = 8, count = 0.
• Row 2: From 8: "rld" (3) + " " + "he" (2) = 6 ≤ 8, start += 8 = 16, count = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        # Step 1: Join sentence with spaces
        s = " ".join(sentence) + " "
        n = len(s)  # Length including final space

        # Step 2: Initialize tracking
        start = 0  # Pointer in sentence
        count = 0  # Number of full fits

        # Step 3: Process each row
        for _ in range(rows):
            # Move pointer by cols
            start += cols

            # If mid-word, rewind to last space
            if start < n and s[start % n] != " ":
                while start > 0 and s[(start - 1) % n] != " ":
                    start -= 1
            # If at or past sentence end, adjust count
            count += start // n
            start = start % n

        return count

• Line 4-5: Join sentence:
• "a b c " (space at end), length n (e.g., 6).
• Line 8-9: Initialize:
• start: Position in s (0).
• count: Full sentence fits (0).
• Line 12-20: Loop rows times:
• Line 13: Advance start by cols (e.g., 6).
• Line 15-17: If start lands mid-word (not space):
• Rewind to last space (e.g., "hello" at 5, back to 0).
• Line 19-20: Add fits (start // n), wrap start (start % n).
• Line 22: Return total fits.
• Time Complexity: O(rows + n)—rows iterations, rewind bounded by sentence length.
• Space Complexity: O(1)—just the joined string.

This is like scrolling a ticker tape with a fast-forward button!

Alternative Solution: Brute Force Simulation

Why an Alternative Approach?

The brute force simulation method steps through each row and column, placing words and counting fits explicitly. It’s O(rows * cols) time and O(1) space—simpler but slower for large screens. It’s like typing out the text on the screen character-by-character!

How It Works

Picture it as filling the screen:

• Step 1: Loop through rows and cols.
• Step 2: Place words, skip spaces, count fits.
• Step 3: Track word index and fits.

Step-by-Step Example

Example: rows = 3, cols = 6, sentence = ["a","b","c"]

• Row 1: "a b c ", word_idx = 3, count = 1.
• Row 2: "a b c ", word_idx = 3, count = 2.
• Row 3: "a b c ", word_idx = 3, count = 3.
• Result: 2 (two full fits).

Code for Brute Force Approach

Copy codeclass Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        count = 0
        word_idx = 0
        n = len(sentence)

        for _ in range(rows):
            col = 0
            while col < cols:
                word_len = len(sentence[word_idx])
                if col + word_len <= cols:  # Fits word
                    col += word_len + 1     # Word + space
                    word_idx = (word_idx + 1) % n
                    if word_idx == 0:
                        count += 1
                else:
                    break

        return count

• Time Complexity: O(rows * cols)—character-by-character.
• Space Complexity: O(1)—few variables.

It’s a slow screen filler!

Comparing the Two Solutions

• Optimized Iteration (Best):
• Pros: O(rows + n), O(1), fast with patterns.
• Cons: Less intuitive.
• Brute Force (Alternative):
• Pros: O(rows * cols), O(1), straightforward.
• Cons: Slower.

Optimized wins for speed.

Additional Examples and Edge Cases

• 1, 1, ["a"]: 1.
• 2, 3, ["a","b"]: 1.
• 1, 10, ["abc"]: 3.

Optimized handles all.

Complexity Breakdown

• Optimized: Time O(rows + n), Space O(1).
• Brute Force: Time O(rows * cols), Space O(1).

Optimized’s the champ.

Key Takeaways

• Optimized: Skip smart!
• Brute Force: Fill it out!
• Fitting: Words align.
• Python Tip: Strings rock—see [Python Basics](/python/basics).

Final Thoughts: Fit That Text

LeetCode 418: Sentence Screen Fitting in Python is a text-scrolling adventure. Optimized iteration zips through it, while brute force fills it steady. Want more string fun? Try LeetCode 415: Add Strings or LeetCode 68: Text Justification. Ready to fit? Head to Solve LeetCode 418 on LeetCode and scroll that sentence today!