418. Sentence Screen Fitting

Problem Description

In this problem, you are required to determine how many times a sentence can be fitted on a screen. The screen has dimensions defined by rows and cols where rows represent the number of lines on the screen and cols stand for the number of characters that can fit in a single line. The sentence is represented as a list of strings where each string is a word from the sentence.

A few rules need to be followed while placing the sentence on the screen:

1. Words must be put on the screen in the same order as they appear in the sentence.
2. No word should be split over two lines. If a word does not fit at the end of a line, it should be moved to the next line.
3. There must be a single space between two consecutive words on the same line.

The aim is to count the total number of times the sentence can be repeated on the screen under these constraints.

Intuition

The intuition behind the solution is to simulate the process of typing out the sentence on the screen by keeping track of the total number of characters that have been placed on the screen. We then use a variable to keep a count of where the next character would be placed in the sequence of the sentence that is repeated indefinitely.

Here's how the approach operates:

1. We first join all the words of the sentence separated by a space and append a space at the end to account for the separation between end and start of the repeated sentence.
2. This creates a string s which is a template of what we are trying to layout on the screen.
3. A variable cur is used to denote the position in the s string where the next character would be placed on the screen.
4. For each row on the screen, we increment cur by the number of columns cols since each row can hold this many characters.
5. We then check if at this cur position we are at a space character in the string s. If so, it means we can fit exactly up to this word on the current row, and we can move to one character past this position, which means the next word should start at the beginning of next line.
6. If cur doesn't land on a space, it means the last word doesn't fit, and we need to backtrack until we find the space that would mark the end of the last word that fits on the current row.
7. After completing all rows, we calculate how many full passes through the s string we made by dividing cur by the length of s, which tells us how many times the sentence was completely fitted on the screen.

By simulating the typing of the sentence row-by-row and handling the constraints, we can determine the total number of times the sentence can be repeated on the given screen.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution provided is a smart linear time approach, which avoids the more obvious brute force method of trying to lay out the sentence on the screen as you would in real life. Here's how this solution works step by step, diving into the algorithm and the data structures:

• First step is to concatenate all words in the sentence with a space and also append a space at the end. This creates a single string s that represents the pattern of the sentence as it would be typed out.

  1s = " ".join(sentence) + " "

• The length of this string m is stored since we are going to use it often to wrap around when the end of the string is reached.

  1m = len(s)

• The algorithm uses a cursor cur to represent the current position in the string s. Initially, cur is set to 0, as we start at the beginning of the sentence.

• The main loop of the algorithm runs once for every row of the screen. In each iteration:

  1. The cursor cur is moved forward by the number of columns cols as if typing out the characters in the current row.

     1cur += cols

  2. If the character at the new cursor position cur % m (adjusted for wrapping around s) is a space, it means a word ends exactly at the end of the row and we can increment cur to look at the beginning of the next word (assuming it would start on the next row).

     1if s[cur % m] == " ":
     2    cur += 1

  3. If we don't land on a space, we need to backtrack to the previous space. This represents moving the cursor back to the end of the last word that fit completely within the row. The while loop continues to decrement cur as long as the character at the decremented position isn't a space (and cur is not yet 0).

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

• After the loop completes, cur represents the total number of characters that were fitted on the screen. By dividing this by the length of s (m), we get the total number of times the sentence has been fitted onto the screen.

  1return cur // m

This implementation efficiently simulates the typing of the sentence onto the screen, while handling cases where a word doesn't fit at the end of a row and needs to be moved to the next row. It does so without actually iterating over every single character, thereby being more efficient than a brute force approach, and doesn't require complex data structures or patterns—just a careful use of a string and character positioning.

Example Walkthrough

Here's a small example to illustrate the solution approach:

Let's say we have a sentence represented by the list of strings sentence = ["hello", "world"] and a screen with dimensions rows = 2 and cols = 8. Now, let's walk through the algorithm to determine how many times the sentence can be fitted on the screen.

1. We first join the words of the sentence separated by a space and append a space at the end to simulate the space at the end of the sentence when it repeats. Our string s will look like this:

   1s = "hello world "

2. The length of s is calculated:

   1m = len(s)  # m is 12

3. We initialize the cursor cur to zero since we start at the beginning of the sentence:

   1cur = 0

4. Now, for each row on the screen, we do the following:

   • For the first row, we start with cur = 0 and move the cursor forward by cols (8 in this case):

     1cur += cols  # cur becomes 8

     At this position (cur % m), we find that s[8 % 12] (which is s[8]) is a space, indicating the word "world" fitting perfectly at the end of the row. So we increment cur to move to the start of the next word:

     1cur += 1  # cur is now 9

   • For the second row, we again move cur forward by cols (8):

     1cur += cols  # cur becomes 17

     But now, s[17 % 12] (which is s[5]) is not a space; it's the character 'o' from the word "hello". This means the word "hello" does not fit completely and needs to continue on the next line. So we backtrack until we find a space:

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

     After backtracking, cur becomes 12, which is the next position after a space, indicating the start of the next word on a new line.

5. Having processed both rows, we determine the number of times the sentence fitted on the screen by dividing cur by the length of s (m):

   1count = cur // m  # count is 1

   The result is 1, meaning the sentence "hello world" was completely fitted on the screen only once given the dimensions rows = 2 and cols = 8.

This example demonstrates the solution approach to the presented problem efficiently using simple string operations to simulate the process of typing a sentence onto a screen with specific dimensions.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(rows * cols) in the worst case. This is because the code iterates over the number of rows given, and for each row, it may potentially iterate over a number of characters up to the number of cols when adjusting the cur variable to point to the start of the next word. However, the average case time complexity can be better since it's not always that we traverse back the full length of cols for each row.

Space Complexity

The space complexity of the code is O(m) where m is the total length of the string constructed by joining all words in the sentence with spaces, plus an additional space at the end. This additional space is used to signify the separation between the end of the sentence and the beginning when the sentence is to be repeated. No other significant space is used, as the variables used for iteration and indexing are of constant size.

Learn more about how to find time and space complexity quickly using problem constraints.