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 and width. (In Java, our toCharArray method makes this , but we could use .charAt instead).


Analysis written by: @awice.