[Java] Justify text

Given an array of words and a page size, return a list of lines that have been padded to fit the given page size.

If a line can fit only one word or is the last line, pad on the right, otherwise pad between words and add excess padding starting from the left.

This can be done in linear time in the size of the output text by walking on the input array and tracking how many words we are adding to the current line, plus how much space is left.

Whenever we add a word, we also check if we could fit the next, as in that case we would add at least a space on the current line.

When we can't add more words to a line or the line is full, we process all words in the start,end range we found so far and correctly pad between them.

The complexity is in calculating how wide each space should be and how much padding we need to add to those spaces:

spaceSize = (page size - length of words on the line) / (number of words on the line - 1)

Then we need to calculate if there is excess padding which needs to be distributed among those breaking points:

remainingPadding = (page size - length of words on the line) % (number of words on the line - 1)

When we add a word, we add spaceSize spaces after it, then one space from remainingPadding (if any are left) 

In the special case of single word or last line, spaceSize will be 1 and remainingPadding will be 0

We then check if the line has still some space left (only can happen in the special case above) and if so, we add enough padding spaces to the right side. 

We only process each string in input twice (first we read and add, then we push to result) and in terms of spaces we only add the ones required. At most in one line there can be M characters, that's the size of the page so in worst case each line can contain only one word and some spaces, the total amount of characters we process among words and spaces is O(NM) where N is the number of input words and M is the page size. This is linear in the size of the output.

Regarding space, we use a StringBuilder, therefore at most we add M words to it each time, bringing space to O(M).

You can check my implementation of fullJustify on my Gist along with some tests in FullJustifyJTests.