Problem Description

You are given a screen with dimensions rows x cols and a list of words forming a sentence. Your task is to determine how many times the complete sentence can be displayed on the screen.

The rules for displaying the sentence are:

• Words must appear in their original order from the sentence
• A word cannot be split across two lines - if a word doesn't fit on the current line, it must start on the next line
• Consecutive words on the same line must be separated by exactly one space
• After reaching the end of the sentence, you can immediately start displaying it again (the sentence can wrap around)

For example, if you have a sentence ["hello", "world"] and a screen with 2 rows and 8 columns:

• Row 1: hello wo (8 characters)
• Row 2: rld hell (8 characters)

The sentence "hello world" appears once completely, with a second occurrence partially started.

The goal is to count how many complete sentences can fit when using all available rows of the screen optimally.

Intuition

The key insight is to think of the sentence as a circular string that repeats infinitely. Instead of manually placing each word and tracking line breaks, we can simulate "cursor movement" through this infinite string.

Imagine concatenating all words with spaces to form a single string like "hello world " (note the trailing space). If we had unlimited horizontal space, we could just write this string repeatedly: "hello world hello world hello world...".

Now, with the screen constraint, we process row by row:

• Each row allows us to advance our cursor by cols positions in this infinite string
• However, we need to handle word boundaries properly

The clever part is handling word breaks:

1. After advancing by cols positions, if we land on a space character, we're at a perfect word boundary - move forward one more position to start the next word
2. If we land in the middle of a word, we need to backtrack to find the last space (word boundary) to ensure we don't split the word

By tracking our total cursor position after processing all rows, we can determine how many complete sentences we've traversed. Since each complete sentence has length m (including spaces), dividing the final cursor position by m gives us the answer.

This approach transforms a complex 2D placement problem into a simple 1D cursor movement problem, where we only need to track position and handle word boundary adjustments.

Solution Approach

The implementation follows the cursor movement strategy through an infinite repeating sentence string:

1. Create the circular sentence string: Join all words with spaces and add a trailing space: s = " ".join(sentence) + " ". This ensures consistent spacing between word repetitions.

2. Initialize tracking variables:

   • m = len(s) stores the length of one complete sentence
   • cur = 0 tracks our current position in the infinite string

3. Process each row:

   for _ in range(rows):
       cur += cols  # Advance cursor by column width

   After each row, we move forward by cols positions.

4. Handle word boundaries after each row:

   • Check if we landed on a space: if s[cur % m] == " ":
     • If yes, move forward one position to start the next word: cur += 1
   • Backtrack if in middle of a word:

     while cur and s[(cur - 1) % m] != " ":
         cur -= 1

     • Keep moving backward until we find a space (word boundary)
     • The modulo operation % m handles the circular nature of the string

5. Calculate the result: return cur // m

   • Integer division of final cursor position by sentence length gives the number of complete sentences

The modulo operator % m is crucial - it maps any position in the infinite string back to the corresponding position in our base sentence string s. This allows us to check characters without actually creating an infinite string.

The algorithm runs in O(rows × average_word_length) time in the worst case, where we might need to backtrack through an entire word for each row. The space complexity is O(total_sentence_length) for storing the concatenated sentence string.

Example Walkthrough

Let's walk through a concrete example with sentence = ["hello", "world"] and a screen of rows = 2, cols = 8.

Step 1: Create the circular sentence string

• Join words with spaces: s = "hello world "
• Length m = 12 (includes the trailing space)

Step 2: Process Row 1

• Start with cur = 0
• Advance cursor by cols: cur = 0 + 8 = 8
• Check character at position 8 % 12 = 8: s[8] = 'r' (middle of "world")
• Since we're in the middle of a word, backtrack:
  • cur = 7: s[6] = 'w' (still in word)
  • cur = 6: s[5] = ' ' (found space!)
• Stop backtracking at cur = 6

Step 3: Process Row 2

• Current position: cur = 6
• Advance cursor by cols: cur = 6 + 8 = 14
• Check character at position 14 % 12 = 2: s[2] = 'l' (middle of "hello")
• Backtrack to find space:
  • cur = 13: s[1] = 'e' (still in word)
  • cur = 12: s[0] = 'h' (still in word)
  • cur = 11: s[11] = ' ' (found space at end of sentence!)
• Stop backtracking at cur = 11

Step 4: Calculate result

• Final cursor position: cur = 11
• Complete sentences: 11 // 12 = 0

This matches our expectation - we couldn't fit even one complete sentence. The screen would show:

• Row 1: "hello " (6 characters used, 2 spaces padding)
• Row 2: "world " (6 characters used, 2 spaces padding)

We've only displayed 11 characters total ("hello world"), missing the final space to complete one full sentence cycle.

Solution Implementation

Time and Space Complexity

Time Complexity: O(rows × cols)

The algorithm iterates through each row exactly once (rows iterations). In each iteration:

• Adding cols to cur takes O(1) time
• Checking if s[cur % m] == " " takes O(1) time
• The while loop in the worst case can backtrack up to cols positions (when an entire row is filled with a single long word that doesn't fit)

Therefore, the worst-case time complexity is O(rows × cols).

Space Complexity: O(n × k)

Where n is the number of words in the sentence and k is the average length of each word.

• The string s is created by joining all words in the sentence with spaces, resulting in a string of length proportional to the total characters in all words plus spaces
• This requires O(n × k) space to store the concatenated string
• All other variables (m, cur, loop counter) use constant O(1) space

The overall space complexity is O(n × k).

Common Pitfalls

1. Not Handling the Circular Nature Correctly

A common mistake is forgetting to use the modulo operator when checking characters, which leads to index out of bounds errors:

Incorrect:

if sentence_string[current_position] == " ":  # IndexError when current_position >= sentence_length
    current_position += 1

Correct:

if sentence_string[current_position % sentence_length] == " ":
    current_position += 1

2. Infinite Loop During Backtracking

The backtracking logic can cause an infinite loop if not bounded properly. Consider when current_position becomes 0:

Problematic:

while sentence_string[(current_position - 1) % sentence_length] != " ":
    current_position -= 1

If current_position reaches 0 and the condition is still true, (current_position - 1) % sentence_length becomes (-1) % sentence_length, which in Python equals sentence_length - 1. This could continue indefinitely if there's no space at that position.

Solution:

while current_position > 0 and sentence_string[(current_position - 1) % sentence_length] != " ":
    current_position -= 1

Adding the current_position > 0 check prevents negative indices and ensures termination.

3. Forgetting the Trailing Space

Without adding a trailing space to the sentence string, word boundaries between sentence repetitions won't be handled correctly:

Incorrect:

sentence_string = " ".join(sentence)  # No trailing space

This causes issues when one sentence ends and another begins - there would be no space separator between the last word of one instance and the first word of the next.

Correct:

sentence_string = " ".join(sentence) + " "

4. Off-by-One Error in Space Handling

When landing on a space, forgetting to advance the cursor by 1 position causes the next row to start with a space:

Incorrect:

if sentence_string[current_position % sentence_length] == " ":
    pass  # Forgot to increment

Correct:

if sentence_string[current_position % sentence_length] == " ":
    current_position += 1  # Skip the space for the next row

5. Edge Case: Single Long Word

If a single word is longer than cols, the backtracking logic could move current_position back to 0 or negative values. While the provided solution handles this with the current_position > 0 check, it's important to note that in such cases, the function correctly returns 0 (no complete sentences can fit).

Test Case to Verify:

sentence = ["verylongword"]
rows = 4
cols = 5
# Expected output: 0 (word doesn't fit in any row)