We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sentence Screen Fitting

Number: 418

Difficulty: Medium

Paid? Yes

Companies: Google, TikTok

Problem Description

Given a screen with a specified number of rows and columns, and a sentence as a list of words, determine how many times the entire sentence can be fitted on the screen. Words cannot be split between lines, and a single space is required between consecutive words. The order of the words must remain unchanged.

Key Insights

  • Concatenate the words of the sentence into a single string with spaces (and an extra space at the end) to simulate continuous placement.
  • Use modulo arithmetic to simulate wrapping around the sentence.
  • For each row, determine how many characters (including spaces) can be placed. If placement ends in the middle of a word, adjust the pointer so that the word is not split.
  • The total count divided by the length of the concatenated string indicates how many times the sentence fits on the screen.

Space and Time Complexity

Time Complexity: O(rows) – We iterate through each row, and adjustments inside the loop are done in constant time on average. Space Complexity: O(1) – Only a few extra variables are used regardless of input size.

Solution

The solution first forms a concatenated string from the sentence with an extra space at the end. This string represents the ideal continuous "line" of text if the sentence were repeated ad infinitum. For each row, we simulate filling columns by adding the number of columns to a pointer that tracks the current position in this long string.

If the pointer lands on a space, we can move to the next character safely. If not, we backtrack to ensure that we are not breaking a word. This adjustment is necessary because words cannot be split between rows. After processing all rows, the number of times the sentence has been fully displayed is equal to the integer division of the pointer by the length of the concatenated sentence string.

Key data structures and techniques:

  • String manipulation for concatenation.
  • Looping through rows.
  • Modulo arithmetic to simulate cyclic iteration over the string.
  • Pointer adjustments to ensure word boundaries.

Code Solutions

# Python solution for Sentence Screen Fitting

def wordsTyping(sentence, rows, cols):
    # Join the sentence into a single string with an extra space at the end.
    s = " ".join(sentence) + " "
    s_length = len(s)
    pointer = 0  # This pointer counts how many characters have been placed
    
    # Process each row on the screen
    for _ in range(rows):
        pointer += cols  # Add maximum number of columns to pointer
        # If pointer is at a space, we can move it forward one to skip the space.
        if s[pointer % s_length] == " ":
            pointer += 1
        else:
            # Otherwise, backtrack to the previous space to avoid splitting a word.
            while pointer > 0 and s[(pointer - 1) % s_length] != " ":
                pointer -= 1
    # The number of times the sentence fits is pointer divided by the length of s.
    return pointer // s_length

# Example test cases
print(wordsTyping(["hello", "world"], 2, 8))  # Expected output: 1
print(wordsTyping(["a", "bcd", "e"], 3, 6))     # Expected output: 2
print(wordsTyping(["i", "had", "apple", "pie"], 4, 5))  # Expected output: 1
← Back to All Questions