Sentence Screen Fitting - Practice Coding Problems

Sentence Screen Fitting - Problem

Given a rows × cols screen and a sentence represented as a list of strings, return the number of times the given sentence can be fitted on the screen.

The order of words in the sentence must remain unchanged, and a word cannot be split into two lines. A single space must separate two consecutive words in a line.

Constraints:

A word can only be placed on a line if it fits completely
Words must appear in order
Each line can contain multiple words separated by single spaces
Count how many complete sentences fit on the screen

Input & Output

Example 1 — Basic Case

$ Input: sentence = ["hello", "world"], rows = 2, cols = 8

› Output: 1

💡 Note: Row 1: "hello wo" (8 chars), Row 2: "rld hello" (9 chars, but only 8 fit: "rld hell"). One complete sentence "hello world" fits.

Example 2 — Multiple Sentences

$ Input: sentence = ["a", "bcd", "e"], rows = 3, cols = 6

› Output: 2

💡 Note: Row 1: "a bcd e" (7 chars, fits as "a bcd "), Row 2: "e a bcd" (7 chars, fits as "e a bc"), Row 3: "d e a b" (7 chars, fits as "d e a "). Two complete sentences fit.

Example 3 — Single Long Word

$ Input: sentence = ["hello-world"], rows = 1, cols = 10

› Output: 0

💡 Note: The word "hello-world" has 11 characters but column limit is 10, so it cannot fit at all.

Constraints

1 ≤ sentence.length ≤ 100
1 ≤ sentence[i].length ≤ 80
sentence[i] consists of only lowercase English letters
1 ≤ rows, cols ≤ 2 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Sentence ["hello", "world"] and 2×8 screen

Process

Place words row by row with proper spacing

Output

Count complete sentences that fit

Key Takeaway

🎯 Key Insight: Track word positions across rows to count complete sentence cycles efficiently

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to simulate word placement row by row while tracking complete sentence cycles. The best approach uses memoization to cache word fitting patterns, avoiding redundant calculations. Time: O(sentence_length + rows), Space: O(sentence_length)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming Approach	O(sentence_length + rows)	O(1)	Use DP to calculate total characters placed and derive sentence count
Optimized with Memoization	O(sentence_length² + rows)	O(sentence_length)	Cache word placement results to avoid recalculating same positions
Brute Force Simulation	O(rows × sentence_length)	O(1)	Simulate placing words row by row, counting complete sentences

Dynamic Programming Approach — Algorithm Steps

Step 1: Calculate total sentence length with spaces
Step 2: For each row, determine max characters that fit
Step 3: Track total characters placed across all rows
Step 4: Divide by sentence length to get complete sentences

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate

Find total length of one complete sentence

Multiply

Total screen capacity = rows × cols

Divide

Complete sentences = total chars ÷ sentence length

Result

Return the quotient as final count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char sentence[][100], int sentenceLen, int rows, int cols) {
    if (sentenceLen == 0 || rows == 0 || cols == 0) {
        return 0;
    }
    
    // Calculate total length needed for one complete sentence
    int totalSentenceLen = 0;
    for (int i = 0; i < sentenceLen; i++) {
        totalSentenceLen += strlen(sentence[i]);
    }
    totalSentenceLen += sentenceLen - 1; // spaces between words
    
    if (totalSentenceLen > cols) {
        // Need to fit words individually
        int wordIdx = 0;
        int sentenceCount = 0;
        
        for (int row = 0; row < rows; row++) {
            int colUsed = 0;
            while (colUsed < cols) {
                int wordLen = strlen(sentence[wordIdx]);
                int needed = wordLen + (colUsed > 0 ? 1 : 0);
                
                if (colUsed + needed > cols) {
                    break;
                }
                
                colUsed += needed;
                wordIdx = (wordIdx + 1) % sentenceLen;
                
                if (wordIdx == 0) {
                    sentenceCount++;
                }
            }
        }
        
        return sentenceCount;
    }
    
    // If sentence fits in one row, calculate directly
    long long totalChars = (long long) rows * cols;
    return totalChars / (totalSentenceLen + 1); // +1 for space between sentences
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char sentence[50][100];
    int sentenceLen = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL) {
        while (*token == ' ') token++;
        if (strlen(token) > 0) {
            strcpy(sentence[sentenceLen], token);
            sentenceLen++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    int rows, cols;
    scanf("%d", &rows);
    scanf("%d", &cols);
    
    int result = solution(sentence, sentenceLen, rows, cols);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(sentence_length + rows)

One pass to calculate sentence length plus one pass through rows

✓ Linear Growth

Space Complexity

O(1)

Only using constant variables for calculations

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler