Text Justification

GIVEN: a string array of words and a numeric width maxWidth,
format and return the text such that each line has exactly
maxWidth characters and is fully (left and right)
justified.

SPECIFICATIONS:
You should pack your words in a greedy approach;
that is, pack as many words as you can in each line.
Pad extra spaces ‘ ‘ when necessary so that each of N lines
has exactly maxWidth letters of time complexity for that line and maxWidth space complexity because we only look at one line at a time…

SPACING rules:
Extra spaces between words should be distributed as
evenly as possible. If the number of spaces on a line
do not divide evenly between words, the empty slots on
the left will be assigned more spaces than the slots
on the right. For the last line of text, it should be
left justified and no extra space is inserted between words.

CONSTRAINTS on parameters:
A word is DEFINED as a character sequence consisting of
non-space characters only. Each word’s length is guaranteed
to be greater than 0 and not exceed maxWidth. The input array
words contains at least one word.¹

— Example 1:

Input: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
Output:
[
“This is an”,
“example of text”,
“justification. “
]

— Example 2:

Input: words = [“What”,”must”,”be”,”acknowledgment”,”shall”,”be”], maxWidth = 16
Output:
[
“What must be”,
“acknowledgment “,
“shall be “
]¹

Approach: Line by line (greedy; each line is made without regard to the previous result)

For each line, get the window for the words which fit in it. Keep track of the length of the window from start to end assuming there’s only one space as a minimum requirement (len).

Count space holders (places between words).²

— Example:

“THIS IS AN”.

len == 10 and count == 2.

(The helper function addLine() creates a new line, while keeping track of:

• same: the base number of spaces every word pair will have between them. This is always the same.
• extra: the extra spaces. Prefer the empty slots on the left.
• trail: only for cases such as last line or there’s only one word in the line. This is the number of spaces at the trail end of the line).³

Start the fullJustify function by making the solution array. For each line, we want to get the window of words which can fit in the line. len is the total number of characters for the line. start is the index at which we start traversing the given words array.⁴

As long as we didn’t reach maxWidth, let’s add more words to that line. Then, we want to figure out the number of non-space characters in the line plus one space between each word, call it len, and we want to figure out the number of space holders, or gaps between words for the line, call it count.⁵

Because one space is the minimum requirement for separating words, and provided that len rapidly keeps track of the character count for this line assuming exactly one space after words (we want one space between words) through incrementing len by the word length and by 1 for one space at once. Increment count by 1, where count keeps track of the number of spaces in the string. We reach the maximum width allocated to each line, at which point we need to delete the last space which has been added by decrementing the end index, one step back to the start index.⁶

var fullJustify = function(words, maxWidth) {
    let result = new Array();
    
    let len = -1, count = -1, start = 0; 
    
    for (let i = 0; i < words.length; i++) { 
        if (len + words[i].length + 1 <= maxWidth) {
            len += words[i].length + 1; 
            count++; 
        }
        else {
            addLine(words, start, i - 1, len, 
                    count, maxWidth, result, false);
            start = i;
            i--;
            len = -1;
            count = -1;
        }
    }
    addLine(words, start, words.length - 1, len, 
            count, maxWidth, result, true);
    return result;
};⁷

The cumulative number of new spaces available, for which the variable count keeps track of existing space holders (the places between words) in the string, that is spaces is the cumulative new spaces available plus the already existing count spaces.⁸

same is the approximate number of spaces every word pair will have between them. If this is the last line, then isLast is true so then we’re going to have exactly one space between words if space holders exist (if there’s more than one word). And of course, if count (the number of gaps between words) is already 0 then there are no spaces between words.⁹

The extra spaces, given one by one from the left and decremented one by one whenever we are done distributing spaces among each space holder, at which point we are left with (spaces % count).

We want trail to keep track of the trail number of space to the line. This is for cases such as 1. last line or 2. only word in the line.

When the index k is still less than the equal number of spaces separating each word referred to by same, and when we haven’t reached the end, keep adding spaces to the line. Because we want the next word to have enough spaces separating it from the previous word.¹⁰

Add any extra spaces (they should be distributed as evenly as possible, so add them first before the left side of the next word at start + 1).

Continue traversing the word list and append the trailing spaces if need be.¹¹

var addLine = function(words, start, end, len, count, maxWidth, result, isLast) {
    let spaces = maxWidth - len; 
    
    spaces += count; 
    
    let same = isLast || (count == 0) ? 0 : Math.floor(spaces/count);
    
    let extra = isLast || (count == 0) ? count : spaces % count;
    
    let trail = isLast || (count == 0) ? maxWidth - len : 0; 
    
    let line = '';
    
    while (start <= end) {
        line += words[start];
        
        for (let k = 0; k < same && start !== end; k++) {
            line += ' ';
        }
        if (extra > 0) { 
            line += ' ';
            extra--;
        }
        start++; 
    } 
    while (trail > 0) {
        line += ' ';
        trail--;
    }
    result.push(line);
}¹²

[1] Text Justification — LeetCode https://leetcode.com/problems/text-justification/

[2] Word Wrap Problem | DP-19 — GeeksforGeeks
https://www.geeksforgeeks.org/word-wrap-problem-dp-19/

[3] What’s the simplest way to strip trailing whitespace from all lines in a file? — Vi and Vim Stack Exchange
https://vi.stackexchange.com/questions/454/whats-the-simplest-way-to-strip-trailing-whitespace-from-all-lines-in-a-file

[4] Justify the given Text based on the given width of each line — GeeksforGeeks
https://www.geeksforgeeks.org/justify-the-given-text-based-on-the-given-width-of-each-line/

[5] Blackmagic Forum • View topic — Text Wrap
https://forum.blackmagicdesign.com/viewtopic.php?f=33&t=114225

[6] Python program for word guessing game — GeeksforGeeks
https://www.geeksforgeeks.org/python-program-for-word-guessing-game/

[7] [Java/C++/Python/JavaScript/Kotlin/Swift]O(n)time/BEATS 99.97% MEMORY/SPEED 0ms APRIL 2022 — Text Justification — LeetCode
https://leetcode.com/problems/text-justification/solutions/1987109/JavaC++PythonJavaScriptKotlinSwiftO(n)timeBEATS-99.97-MEMORYSPEED-0ms-APRIL-2022

[8] Rearrange Spaces Between Words — LeetCode
https://leetcode.com/problems/rearrange-spaces-between-words/

[9] Spaces Between Sentences and Words: How Many Should You Use?
https://prowritingaid.com/spaces-between-sentences-and-words

[10] How to find index of an exact word in a string in Python — Stack Overflow
https://stackoverflow.com/questions/38956274/how-to-find-index-of-an-exact-word-in-a-string-in-python

[11] Remove extra spaces from a string — GeeksforGeeks
https://www.geeksforgeeks.org/remove-extra-spaces-string/

[12] Complexity and Big-O Notation
https://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html