# A simple simulation

• We spend `O(n)` time on padding each row, resulting in an `O(n * rows)`-time solution. Here, `n` denotes the number of sentences.
Conceptually, each row consists of the following three parts:

1. a nullable suffix of the given list, followed by
2. as many as complete given lists, followed by
3. a nullable proper prefix of the given list

Part 1 and 3 can be handled by brute-force in `O(n)` time, and part 2 can be done in `O(1)` time via a division after we pre-compute the total length of the sentences. Therefore, the overall runtime is `O(n * rows)`.

``````public class Solution {
public int wordsTyping(String[] sentence, int rows, int cols) {
int sum = 0, ans = 0, which = 0;
for (String s : sentence) sum += s.length();
for (int i = 0; i < rows; i++) {
int remaining = cols + 1; // reserve an extra space for the dummy space to the left of the first letter
while (which < sentence.length && sentence[which].length() + 1 <= remaining)
remaining -= sentence[which++].length() + 1;
if (which >= sentence.length) {
which = 0;
ans = ans + 1 + remaining / (sum + sentence.length);
remaining %= sum + sentence.length;
while (which < sentence.length && sentence[which].length() + 1 <= remaining)
remaining -= sentence[which++].length() + 1;
}
}
return ans;
}
}
``````

• Excellent solution!

• Nice solution! Just for a little bit simplicity, no need to suffix and prefix(for the first while loop in for loop), just count how many whole length and start from last index, see my c++ code

``````class Solution {
public:
int wordsTyping(vector<string>& sentence, int rows, int cols) {
int sum = 0;
for (auto s: sentence) {
if (s.size() > cols) {
return 0;
}
sum += s.size()+1;
}
int length = sentence.size();
int index = 0, count = 0;
for (int i = 0; i < rows; i++) {
int locations = cols + 1;
count += locations / sum;
locations %= sum;
while (locations >= sentence[index].size() + 1) {
locations -= sentence[index++].size() + 1;
if (index == length) {
count++;
index = 0;
}
}
}
return count;
}
};
``````

• If you compute a running sum of the lengths of the words in a sentence, it seems like you can use binary search to find how many words in the prefix and suffix sentence you can add, using the number of columns left as a key.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.