Sorry for the ugly code, not sure how to make it cleaner. Here are the key points being used to make it O(n).

When
cols
is really large, findlength
of a complete sentence and shrink cols to a smaller size.
i). For example:cols = max( 0, ((cols+1)%(length+1))1 );
This takes O(n) time.
ii). Also, keep track ofnumSentenceInRow = (cols+1)/(total+1);
. 
Build a DP table, where
DP[i]=j
means that if a line start with thei
th word, then the next line will start with thej
th word. Using a sliding window approach, this will take O(n) time, sincecols
is now<length
. 
Finally to handle large
rows
, we will useDP
table to find the period where the first word start repeating.
i). For example, the pattern may look like this0>7>4>1>8>5>2>8>5>2...
O(n) time since cycle cannot be longer thann
.
ii) Shrink the number of rows to newRows as follows:
if( rows > n ) {
newRows = (rowsn)%period + n;
numCycle = (rowsn)/period;
}

Compute the number of sentences in each
cycle
and in the firstnewRows
. O(n) time sincenewRows<2*n
.
Total = numCycle*numSentenceInCycle + numSentence + rows*numSentenceInRow
My ugly code...
class Solution {
vector<int> dp, visited;
public:
int wordsTyping(vector<string>& sentence, int rows, int cols) {
int total = 1, n = sentence.size();
dp = vector<int>( 2*n , 0 );
visited = vector<int>( 2*n , 1 );
//if cols is too large, check for cycle and shrink it
for( auto w: sentence ) total += w.size() + 1;
int numSentenceInRow = (cols+1)/(total+1);
cols = max( 0, ((cols+1)%(total+1))1 );
//build dp table using sliding window for o(n) performance
total = 1;
int j = 0;
for( int i = 0; i< n*2; i ++){
int k = i%n;
while( total + 1 + (int)sentence[k].size() > cols ){
dp[j%n] = k;
total = total  ( 1 + sentence[(j++)%n].size() ) ;
}
total += (1 + sentence[k].size());
}
//find cycle
int curr = 0, i = 0, count = 0;
while( visited[curr] == 1 ){
visited[curr] = i++;
curr = dp[curr];
}
int period = ivisited[curr], start = curr;
int newRows = rows, numCycle = 0;
//if rows is too large, check for cycle and shrink it
if( rows > n ) {
newRows = (rowsn)%period + n;
numCycle = (rowsn)/period;
}
//count number of sentence in each cycle o(n)
int numSentenceInCycle = dp[start] < start;
curr = dp[start];
while( curr != start ){
if( dp[curr] < curr ) numSentenceInCycle ++;
curr = dp[curr];
}
//count number of sentence in first few lines o(n)
int numSentence = 0;
curr = 0;
for( int m = 0; m < newRows; m ++){
if( dp[curr] < curr ) numSentence ++;
curr = dp[curr];
}
return numCycle*numSentenceInCycle + numSentence + rows*numSentenceInRow;
}
};