Approach #1: Insert Each Character [Accepted]
Intuition
We can write out each character in the string S
one by one.
As we write characters, we can update (lines, width)
that keeps track of how many lines we have used, and what is the length of the used space in the last line.
Algorithm
If the space w
of the next character in S
fits our current line, we will add it. Otherwise, we will start a new line, and use w
space to put that character on the next line.
Complexity Analysis

Time Complexity: , as we iterate through
S
. 
Space Complexity: additional space, as we only use
lines
andwidth
. (In Java, ourtoCharArray
method makes this , but we could use.charAt
instead).
Analysis written by: @awice.