Simple C++ solution optimized by some arithmetic

• Simple algorithm.

1. Skip to the point in the current column where the sentence won't fit in the same row anymore.
2. Once we have `r` rows fully (all columns in those rows as well) filled by `k` repetition of sentence, we know every following `r` rows will have `k` repetitions. Skip to the last `total_rows % r` rows.

Worst Case Complexity: `O(n*frows)`
`n` is total length of the sentence
`frows` is min # of rows to fully contain `k` sentence repetitions

Commented as much as possible.

``````    int wordsTyping(vector<string>& sentence, int rows, int cols) {

int i = 0, j = 0; // row and column pointers
int res = 0; // total repetitions

int total_size = 0; // total size of sentence
for (string& s : sentence) {
total_size += s.size();
}

while (i < rows && j < cols) {
int s = 0; // index into sentence vector

// skip to the column where splitting of the sentence takes place
int occupied_size = total_size + sentence.size(); // with spaces
int repeat_in_row = (cols - j)/occupied_size; // repetitions
res += repeat_in_row;
j += repeat_in_row * occupied_size; // remaining column
if (j == cols) {
++i; j = 0; // move to the next row
--res; // hack to let the later if statement to handle ++res
s = sentence.size(); // we are done with the sentence
}

// this is to go over multiple rows for a single sentence iteration
while (s < sentence.size() && i < rows && j < cols) {
int n = sentence[s].size();
if (j + n > cols) { // doesn't fit
++i;
j = 0;
} else if ((j + n == cols) || (j + n == cols - 1)) { // just fits or just fits with space
++i;
j = 0;
++s;
} else { // fits
j += n + 1;
++s;
}
}

if (s == sentence.size()) {
++res;
if (j == 0) { // end of column
res *= rows/i; // repeat total res as many i sized rows as possible
i = rows - rows%i; // remaining rows
}
} else {
break;
}
}

return res;
}
``````

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