# 99% 0ms O(n) c++ solution where n = #words. Detailed explanation and analysis included.

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

1. When `cols` is really large, find `length` 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 of `numSentenceInRow = (cols+1)/(total+1);`.

2. Build a DP table, where `DP[i]=j` means that if a line start with the `i`th word, then the next line will start with the `j`th word. Using a sliding window approach, this will take O(n) time, since`cols` is now `<length`.

3. Finally to handle large `rows`, we will use `DP` table to find the period where the first word start repeating.
i). For example, the pattern may look like this `0->7->4->1->8->5->2->8->5->2...` O(n) time since cycle cannot be longer than `n`.
ii) Shrink the number of rows to newRows as follows:
`if( rows > n ) {`
`newRows = (rows-n)%period + n;`
`numCycle = (rows-n)/period;`
`}`

4. Compute the number of sentences in each `cycle` and in the first `newRows`. O(n) time since `newRows<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 = i-visited[curr], start = curr;
int newRows = rows, numCycle = 0;

//if rows is too large, check for cycle and shrink it
if( rows > n ) {
newRows = (rows-n)%period + n;
numCycle = (rows-n)/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;
}
};
``````

• Nice solution! I have one question: while shrinking the number of rows, why do (rows - n)? Thanks.

• Let p = period, I think sometimes, the pattern doesn't appear within the first p lines, for example
`0->7->4->1->8->5->2->8->5->2...`
I am doing that to make sure that there are enough rows for the pattern to appear.

• dp = vector<int>( n , 0 ); is what's required. I think the 2*n was there only due to historical reason. Good solution!

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