Jobs

Interviews

Discussions

Sentence Screen Fitting

Medium

Asked by:

3 views

Topics:

ArraysStrings

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

A word cannot be split into two lines.
The order of words in the sentence must remain unchanged.
Two consecutive words in a line must be separated by a single space.
Total words in the sentence won't exceed 100.
Length of each word is greater than 0 and won't exceed 10.
1 <= rows, cols <= 20,000.

Example 1:

Input:
sentence = ["hello", "world"]
rows = 2
cols = 8
Output: 
1
Explanation:
hello--- 
world---

Character '-' signifies an empty space on the screen.

Example 2:

Input:
sentence = ["a", "bcd", "e", "f"]
rows = 3
cols = 6
Output: 
2
Explanation:
a-bcd- 
e-f--  
a-bcd- 

Character '-' signifies an empty space on the screen.

Example 3:

Input:
sentence = ["i", "had", "applepie"]
rows = 4
cols = 5
Output: 
1
Explanation:
i-had
apple
pie-i
had--

Character '-' signifies an empty space on the screen.

Sentence Screen Fitting

Medium

Asked by:

3 views

Topics:

ArraysStrings

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

A word cannot be split into two lines.
The order of words in the sentence must remain unchanged.
Two consecutive words in a line must be separated by a single space.
Total words in the sentence won't exceed 100.
Length of each word is greater than 0 and won't exceed 10.
1 <= rows, cols <= 20,000.

Example 1:

Input:
sentence = ["hello", "world"]
rows = 2
cols = 8
Output: 
1
Explanation:
hello--- 
world---

Character '-' signifies an empty space on the screen.

Example 2:

Input:
sentence = ["a", "bcd", "e", "f"]
rows = 3
cols = 6
Output: 
2
Explanation:
a-bcd- 
e-f--  
a-bcd- 

Character '-' signifies an empty space on the screen.

Example 3:

Input:
sentence = ["i", "had", "applepie"]
rows = 4
cols = 5
Output: 
1
Explanation:
i-had
apple
pie-i
had--

Character '-' signifies an empty space on the screen.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input words array contain empty strings, and if so, how should I handle them?
Are `rows` and `cols` guaranteed to be positive integers?
If a sentence cannot fit even a single time, what value should I return?
Can I assume all words in the sentence are shorter than `cols`?
Does the sentence end with whitespace, and should I account for that when fitting the words?

Brute Force Solution

Approach

The brute force approach to fitting a sentence onto a screen means we try every possible way to arrange the words. We essentially simulate writing the sentence repeatedly onto the screen, counting how many times the entire sentence fits without going over the screen's boundaries.

Here's how the algorithm would work step-by-step:

Imagine you're manually typing the sentence onto the screen.
Start with the first word of the sentence.
Check if the first word fits on the first line.
If it does, move to the next word and see if it also fits on the same line with a space in between.
Continue adding words until the line is full or you run out of words from the sentence.
If the line is full but you haven't used all the words from the sentence, move to the next line and start again from where you left off in the sentence.
Repeat this process, line by line, until you've filled the entire screen or you've determined the sentence cannot fit any further.
Keep track of how many complete times you wrote the entire sentence before you filled the screen.
That count represents how many times the sentence fits completely.

Code Implementation

def fitting_sentence_brute_force(sentence, rows, columns):
    sentence_length = len(sentence)
    sentence_string = ' '.join(sentence)
    sentence_string_length = len(sentence_string)
    sentence_index = 0
    times_sentence_appears = 0

    for row_index in range(rows):
        current_column_length = 0

        # Iterate until the current row is full.
        while current_column_length + len(sentence[sentence_index % sentence_length]) <= columns:
            word_length = len(sentence[sentence_index % sentence_length])

            # Check if adding current word exceeds column limit.
            if current_column_length + word_length <= columns:
                current_column_length += word_length

                # Increment sentence index and column length if a space is needed.
                if current_column_length < columns:
                    current_column_length += 1

                sentence_index += 1

                # Count complete sentences.
                if sentence_index >= sentence_length and sentence_index % sentence_length == 0:
                    times_sentence_appears += 1
            else:
                break

    return times_sentence_appears

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(rows * cols) – The algorithm simulates writing the sentence onto the screen row by row. The outer loop iterates through each row of the screen, which is 'rows'. In the inner loop, we simulate fitting words onto the current line until it's full (up to 'cols' characters). Therefore, in the worst-case scenario, we might have to iterate through each cell of the screen. The number of operations is roughly proportional to rows * cols, which gives us a time complexity of O(rows * cols).

Space Complexity

O(1) – The brute force approach simulates typing the sentence and counts how many times the sentence fits. It primarily uses variables to track the current row, column, and word index. No additional data structures like arrays or hash maps are created to store intermediate results. The space required remains constant regardless of the sentence length or screen dimensions, thus the space complexity is O(1).

Optimal Solution

Approach

The key to solving this efficiently is to simulate how many times the sentence can fully fit on the screen before needing to consider partial repetitions. We pre-calculate some information about the sentence and screen dimensions to avoid redundant computations.

Here's how the algorithm would work step-by-step:

Combine the words of the sentence into one long string, separated by single spaces. This simplifies calculations later on.
Figure out how many times you can put the entire combined sentence onto the screen. This is done by walking through the screen row by row and counting how many characters are consumed from the combined sentence.
Since we're using the combined sentence, account for looping back to the beginning if you reach the end.
Take the integer division of the consumed characters divided by the length of the combined sentence to derive the full repeats
Keep track of where you stopped in the combined sentence after the full repeats.
For the remainder, do a little extra processing to handle the words that partially fit the screen at the end.
The total number of complete sentence repetitions is your answer.

Code Implementation

def sentence_screen_fitting(sentence, rows, columns):
    combined_sentence = ' '.join(sentence) + ' '
    sentence_length = len(combined_sentence)
    characters_consumed = 0

    for _ in range(rows):
        characters_consumed += columns

        # Adjust for spaces or partial words at the end of the row.
        if combined_sentence[characters_consumed % sentence_length] == ' ':
            characters_consumed += 1
        elif combined_sentence[(characters_consumed % sentence_length) - 1] != ' ':

            # Backtrack to the beginning of the last word.
            while characters_consumed > 0 and combined_sentence[(characters_consumed % sentence_length) - 1] != ' ':
                characters_consumed -= 1

    # Calculate how many times sentence was fully repeated
    full_repeats = characters_consumed // sentence_length
    return full_repeats

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(rows) – The primary cost driver of this algorithm is the simulation of filling the screen row by row. The algorithm iterates through each of the 'rows' on the screen. Inside this loop, the computation involves incrementing the combined sentence index and checking if the current row can accommodate the next word. Therefore the number of rows is what determines the overall runtime. Thus, the overall time complexity is O(rows).

Space Complexity

O(N) – The solution concatenates the input sentence words into a single string with spaces in between. The length of this combined string is proportional to the total number of characters across all the words in the input sentence, plus the spaces separating them. Therefore, the auxiliary space required to store the combined string grows linearly with N, where N is the total length of all words in the sentence. This dominates any constant space usage, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty sentence array	Return 0 immediately as no words exist to fit the screen.
Empty row or cols	Return 0 if either rows or cols are zero because nothing can be fit.
A single word longer than cols	Return 0 immediately, because the word cannot fit in a row.
Sentence contains an empty string	Treat the empty string as a valid, albeit zero-length, word.
Very large sentence size (memory implications)	The solution needs to avoid creating excessively large intermediate strings representing the entire sentence repeated many times to prevent memory issues, and instead use modular arithmetic
Large rows and cols (potential integer overflow)	Ensure the calculations involving rows and cols don't lead to integer overflows; use long or appropriate data type if necessary.
cols is large, but sentence can be fit many times	Optimize fitting multiple sentences on a row efficiently without iterating unnecessarily.
Sentence with leading or trailing spaces in words	Trim the leading/trailing spaces of each word in the input sentence to ensure accurate fitting.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input words array contain empty strings, and if so, how should I handle them?
Are `rows` and `cols` guaranteed to be positive integers?
If a sentence cannot fit even a single time, what value should I return?
Can I assume all words in the sentence are shorter than `cols`?
Does the sentence end with whitespace, and should I account for that when fitting the words?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're manually typing the sentence onto the screen.
Start with the first word of the sentence.
Check if the first word fits on the first line.
If it does, move to the next word and see if it also fits on the same line with a space in between.
Continue adding words until the line is full or you run out of words from the sentence.
If the line is full but you haven't used all the words from the sentence, move to the next line and start again from where you left off in the sentence.
Repeat this process, line by line, until you've filled the entire screen or you've determined the sentence cannot fit any further.
Keep track of how many complete times you wrote the entire sentence before you filled the screen.
That count represents how many times the sentence fits completely.

Code Implementation

def fitting_sentence_brute_force(sentence, rows, columns):
    sentence_length = len(sentence)
    sentence_string = ' '.join(sentence)
    sentence_string_length = len(sentence_string)
    sentence_index = 0
    times_sentence_appears = 0

    for row_index in range(rows):
        current_column_length = 0

        # Iterate until the current row is full.
        while current_column_length + len(sentence[sentence_index % sentence_length]) <= columns:
            word_length = len(sentence[sentence_index % sentence_length])

            # Check if adding current word exceeds column limit.
            if current_column_length + word_length <= columns:
                current_column_length += word_length

                # Increment sentence index and column length if a space is needed.
                if current_column_length < columns:
                    current_column_length += 1

                sentence_index += 1

                # Count complete sentences.
                if sentence_index >= sentence_length and sentence_index % sentence_length == 0:
                    times_sentence_appears += 1
            else:
                break

    return times_sentence_appears

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Combine the words of the sentence into one long string, separated by single spaces. This simplifies calculations later on.
Figure out how many times you can put the entire combined sentence onto the screen. This is done by walking through the screen row by row and counting how many characters are consumed from the combined sentence.
Since we're using the combined sentence, account for looping back to the beginning if you reach the end.
Take the integer division of the consumed characters divided by the length of the combined sentence to derive the full repeats
Keep track of where you stopped in the combined sentence after the full repeats.
For the remainder, do a little extra processing to handle the words that partially fit the screen at the end.
The total number of complete sentence repetitions is your answer.

Code Implementation

def sentence_screen_fitting(sentence, rows, columns):
    combined_sentence = ' '.join(sentence) + ' '
    sentence_length = len(combined_sentence)
    characters_consumed = 0

    for _ in range(rows):
        characters_consumed += columns

        # Adjust for spaces or partial words at the end of the row.
        if combined_sentence[characters_consumed % sentence_length] == ' ':
            characters_consumed += 1
        elif combined_sentence[(characters_consumed % sentence_length) - 1] != ' ':

            # Backtrack to the beginning of the last word.
            while characters_consumed > 0 and combined_sentence[(characters_consumed % sentence_length) - 1] != ' ':
                characters_consumed -= 1

    # Calculate how many times sentence was fully repeated
    full_repeats = characters_consumed // sentence_length
    return full_repeats

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty sentence array	Return 0 immediately as no words exist to fit the screen.
Empty row or cols	Return 0 if either rows or cols are zero because nothing can be fit.
A single word longer than cols	Return 0 immediately, because the word cannot fit in a row.
Sentence contains an empty string	Treat the empty string as a valid, albeit zero-length, word.
Very large sentence size (memory implications)	The solution needs to avoid creating excessively large intermediate strings representing the entire sentence repeated many times to prevent memory issues, and instead use modular arithmetic
Large rows and cols (potential integer overflow)	Ensure the calculations involving rows and cols don't lead to integer overflows; use long or appropriate data type if necessary.
cols is large, but sentence can be fit many times	Optimize fitting multiple sentences on a row efficiently without iterating unnecessarily.
Sentence with leading or trailing spaces in words	Trim the leading/trailing spaces of each word in the input sentence to ensure accurate fitting.