418

418. Sentence Screen Fitting (Medium)

Given a rows x 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.

 

Example 1:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1
Explanation:
hello---
world---
The character '-' signifies an empty space on the screen.

Example 2:

Input: sentence = ["a", "bcd", "e"], rows = 3, cols = 6
Output: 2
Explanation:
a-bcd- 
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.

Example 3:

Input: sentence = ["i","had","apple","pie"], rows = 4, cols = 5
Output: 1
Explanation:
i-had
apple
pie-i
had--
The character '-' signifies an empty space on the screen.

 

Constraints:

• 1 <= sentence.length <= 100
• 1 <= sentence[i].length <= 10
• sentence[i] consists of lowercase English letters.
• 1 <= rows, cols <= 2 * 104

Companies:
Google, Uber

Related Topics:
String, Dynamic Programming, Simulation

Similar Questions:

• Minimum Cost to Separate Sentence Into Rows (Medium)

Solution 1.

Spent a lot of time making the details correct. Need to find easier solution.

// OJ: https://leetcode.com/problems/sentence-screen-fitting/
// Author: github.com/lzl124631x
// Time: O(N) where N is the length of `A`
// Space: O(N)
class Solution {
public:
    int wordsTyping(vector<string>& A, int rows, int cols) {
        int N = A.size(), mxSize = 0;
        vector<int> sum(N), cntQueue, rowMap(N, -1);
        for (int i = 0, s = 0; i < N; ++i) {
            s += A[i].size();
            if (i > 0) s += 1;
            sum[i] = s;
            mxSize = max(mxSize, (int)A[i].size());
        }
        int repeat = cols / (sum.back() + 1), cnt = 0;
        cols %= sum.back() + 1;
        int ans = repeat * rows;
        if (mxSize > cols) return ans; 
        for (int i = 0, j = 0; i < rows ; ++i) {
            int sum = A[j].size();
            j = (j + 1) % N;
            cnt += j == 0;
            for (; sum + A[j].size() + 1 <= cols; ) {
                sum += A[j].size() + 1;
                j = (j + 1) % N;
                cnt += j == 0;
            }
            int end = (j - 1 + N) % N;
            if (rowMap[end] == -1) {
                rowMap[end] = i;
                cntQueue.push_back(cnt);
            } else {
                int startRow = rowMap[end];
                int c = cnt - cntQueue[startRow];
                int len = i - startRow;
                int r = (rows - startRow) / len;
                if (startRow > 0) ans += cntQueue[startRow - 1];
                ans += r * c;
                int remain = (rows - startRow) % len;
                if (remain) {
                    ans += cntQueue[startRow + remain - 1] - (startRow > 0 ? cntQueue[startRow - 1] : 0);
                }
                return ans;
            }
        }
        return ans + cnt;
    }
};