Solution Explanation

This problem asks to determine how many times a sentence can be fitted onto a screen with a given number of rows and columns. The key constraint is that words cannot be broken across lines, and a space must separate words.

The optimal solution avoids simulating the screen fitting process directly. Instead, it cleverly uses the modulo operator (%) to efficiently track the position in the sentence as it wraps around.

Approach

1. Concatenate: The solution begins by concatenating all words in the sentence array into a single string s, separated by spaces. An extra space is appended to the end to handle cases where a line ends perfectly at the end of a word.

2. Iterate through Rows: The code iterates through each row of the screen. In each iteration:

   • It adds the cols (number of columns) to the cur variable, representing the current character position in the concatenated string s. The modulo operator (% m) ensures that cur wraps around to the beginning of s when it exceeds the length of s (m).

   • Space Check: If the character at cur % m is a space, it means the current position is the end of a word. The cur is incremented to move to the next word.

   • Backtrack for Non-Space: If cur % m is not a space, it signifies that the current line ends mid-word. The code then backtracks (while cur > 0 and s[(cur-1)%m] != " ") to find the end of the previous word, ensuring the entire word fits on the line.

3. Calculate Result: After iterating through all rows, the number of times the sentence fits on the screen is determined by cur // m. This integer division gives the number of complete repetitions of s covered by the cursor position.

Time Complexity Analysis

The time complexity is O(rows + cols), as it iterates through each row once. The inner loop during backtracking has a maximum iteration count proportional to cols in the worst case. The concatenation step is O(n), where n is the length of the sentence. However, since rows and cols are typically larger than the length of the sentence, the overall time complexity is dominated by the row iteration and thus O(rows + cols).

Space Complexity Analysis

The space complexity is O(n), where n is the total number of characters in the concatenated sentence, due to the storage of the concatenated string s. The other variables (cur, m, etc.) use constant space.

Code Examples (with explanations within the code comments)

The code examples in Python, Java, C++, Go, and TypeScript demonstrate the implementation of this efficient approach. The comments in the code explain each step. (See the original response for the code examples in all languages).