Leetcode: Text Justification

This question is asked a lot in Intuit, Twilio, Karat, and Uber, and is ranked as a "hard" question on Leetcode and is as follows: 

Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully justified, and you should pack your work in a greedy approach and pad extra spaces. Extra spaces between words should be distributed as evenly as possible, and for the last line, no extra space is inserted between the words. 

My idea is we need to calculate the size of each space and then add the number such that each line fits exactly 16. 

It's easy if it's one word, since the result is just that word. If it's the last line, then the result is all the words separated by a single space, else calculate the size of the space evenly and distribute the remainders evenly until everything is all gone. Remember, writing code in separate functions is wayyy better than just writing the lines of code in one function. 

Here's an example

The max width is 15 and the array is ["What", "must" "be", "acknowledgement", "shall", "be"].

First get the length of all the words so 4,4,2,14,5,2. 

The output is

[What---must--be.

acknowledgement-. 

shall-be-------]

The second line is left justified because there is only one word that can fit in that line. The first line is middle justified. If we cannot evenly distribute the spaces, then the left-most words need to have the higher number of spaces in comparison to the right words. We need i, j, and linelength. As for j, we're gonna move j forward while adding in the caracter lengths in tehe line length and see if we're over or under the max width. The line length is initialized to whatever the i pointer is looking at, and see if the word can be added to this line. Let's do

4+4+1 = 9 < 15, which is under our max width. The first "4" correlates to "what" and the second "4" correlates to "must". We do add "must" to this line.

Our new line length will be 8 characters. So we do 8, the current line length plus 2 2's, which makes equivalent to "12.". So it comes from Whatmust, and "be" and the 2 spaces that we have to apply between these lines. We do apply the word "be" to this line, so our new line length willl be 4+4+2 = 10. Now we're going to move the j pointer forward to the word "acknowledgement". The minimum spaces we need for these words is 3, and 10+14+3 = 27 > 15, so we can't add the word to this line, and now we need to figure out how we apply the spaces and where we apply them. Now we get the pointer j - i, corresponding to 3 words, with "What", "must", and "be". We need some variables

the diff is the maxWidth - lineLength = 5, so we need 5 spaces. spacesNeeded equals how many times we need to apply spaces inside of the line. The space sections are j - i 0 1 which equal to 2 space sections, and spaces = diff / spacesNeeded - 5/2 - 2, which are 2 spaces applied. The extra spaces tell how many spaces are needed, since we may not be able to distribute all the spaces evenly. So now we have all the variables, and we need a result, keeping track of the output of this line. 

We apply spaces + extraspaces on the left side, then decrement variables down to 0, and we apply 2 spaces to the rest. otherwise, we decrement the other spaces.

What---must--be, so we successfully middle justified this line, and now we need to move the i pointer to the j pointer, and the j pointer moves directly in front of the i pointer.

We do this with acknowledge ment and linelength is 14, and diff = maxWidth - lineLength so spaces on right diff - (j - i - 1) which is equal to the remainder, and we immediately applying, now we have the acknowledgement and now we finished iterating. 

Shall is 5 characters and we want to see if we want to add the word "be" and will make a total length of 8, which now we can apply the "be" to this line. Once we are out of bounds, we need to left justify and append the spaces on the rightmost line. We may determine diff is 15 - 7 = 8, which means the number of spaces on right is 8 - (6 - 4 - 1) = 7, so we add 1 shall with 1 space, and then left append.

Now we want to code the solution to this problem.

class Solution {

    public List<String> fullJustify(String[] words, int maxWidth) {

        int i = 0, n = words.length;

        //go through each of the words

        while(i < n) {

            int j = i + 1;

            int lineLength = words[i].length;

            //while we are going through the line and the word has not reached the end of the line

            while(j < n && lineLength + words[j].length() + (j - i - 1) < maxWidth)) {

                lineLength += words[j].length();

                ++j;

            }

            int diff = maxWidth - lineLength;

            int numberOfWords = j - i;

//if there is only 1 word, left justify and pad on right

            if(numberOfWords == 1 || j >= n){

                result.add(leftJustify(words, diff, i, j));

            } 

            //else justify and pad everything in the middle

            else {

                result.add(middleJustify(words, diff, i, j));

            }

            i = j;          

        }

        return result;

    }

    private String leftJustify(String[] words, int diff, int i, int j) {

//determine the number of spaces there are 

        int spacesOnRight = diff - j - i - 1;

        for(int k = i + 1; k < j; ++k) {

            result.append(" " + words[k]);

        }

        //put this number of spaces

        result.append(" ".repeat(spacesOnRight));

        return result.toString(); 

    }

    public String middleJustify(String[] words, int diff, int i, int j) {

        //number of spaces needed which is the number of words - 1 in line

        int spacesNeeded = j - i - 1;

        //figure out how many spaces you put per word

        int spaces = diff / spacesNeeded;

        //figure out the remainder of the spaces 

        int extraSpaces = diff % spacesNeeded;

        StringBuilder result = new StringBuilder(words[i]);

        //get the number of spaces to apply for extra for every character for every word

        for(int k = i + 1; k < j; ++k) {

            int spacesToApply = spaces + (extraSpaces-- > 0 ? 1 : 0);

        }

        result.append(" ".repeat(spacesToApply) + words[k]);

    }

    return result.toString();

}

As is the code.