Problem

We are given an array of words and also given a maximum width. We have to format the given text in such a way that each line having exactly maximum width characters and each line must be fully justified (left and right). To do so, we need to follow the greedy approach, i.e., pack as many words as we can in each line. If the line does not fill the maximum width, we need to insert spaces between the words until the line is full. These spaces should be distributed as evenly as possible. If the spaces do not divide evenly among the words, we assign more spaces to the slots on the left than the slots on the right.

However, the last line of the text should be left-justified, and no extra space needs to be inserted between words.

Walkthrough

Let's walk through the example where words = ["This", "is", "an", "example", "of", "text", "justification."] and maxWidth = 16.

• First, we start by adding words to the first line. We can fit "This", "is", "an" into the first line with enough spaces to justify the line. The first line becomes "This is an".
• Then, we move to the second line. "example" and "of" can fit into the second line but "text" cannot because it will exceed the maxWidth. We add spaces to justify the line. The second line becomes "example of text".
• Lastly, we are left with "justification.", so we add it to the last line. The last line is left justified as per the instructions. The last line becomes "justification. ".

The output of the problem will be:

1
2
3[
4 "This    is    an",
5 "example  of text",
6 "justification.  "
7]

Approach

In this problem, we try to fit as many words as possible on each line. We then justify the line by adding spaces between the words. If a single word on a line is encountered, all the extra spaces will be added to the right of the word. The last line of the text will be left-justified, and no extra spaces will be inserted between words.

The algorithm follows these steps.

1. Start a line with an empty string and a counter for the number of letters in the line.

2. For each word in the list of words:

   a. If the number of letters and spaces in the line plus the incoming word exceed the maxWidth, conclude the line and add it to the output list.

   b. Distribute the remaining spaces in the line evenly among the gaps between words. For any remaining spaces, add one extra space sequentially from left to right.

   c. If the line only has one word, append all the extra spaces to the right of the word.

   d. If the word doesn't exceed the maxWidth, it's added to the current line.

3. Assemble the last line in the list, which is only left-justified, and add it to the output list.

4. Return the output list of strings.

The key point here is to modularize functions to separate functionality and make the base function cleaner.

Python Solution

1
2python
3class Solution:
4    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
5        res, cur, num_of_letters = [], [], 0
6        for w in words:
7            if num_of_letters + len(w) + len(cur) > maxWidth:
8                if len(cur) == 1:
9                    res.append( cur[0] + ' '*(maxWidth - num_of_letters) )
10                else:
11                    num_spaces = maxWidth - num_of_letters
12                    space_between_words, num_extra_spaces = divmod( num_spaces, len(cur) - 1)
13                    for i in range(num_extra_spaces):
14                        cur[i] += ' '
15                    res.append( (' '*space_between_words).join(cur) )
16                cur, num_of_letters = [], 0
17            cur += [w]
18            num_of_letters += len(w)
19        res.append( ' '.join(cur) + ' '*(maxWidth - num_of_letters - len(cur) + 1) )
20        return res

This problem is using a greedy approach. We hold words in a line until we can't add anymore.

This solution uses the base Python features without importing any library. We calculate remaining slots on a line by checking if line length + incoming word length + number of words in the line > max_width. If so, we go on to distribute extra spaces on a line. If there is only 1 word, we add all the extra spaces to it. If there is more than one word, we distribute the spaces as evenly as possible across the words, and add the remaining slots at the beginning of the line.Then we append this line to our result and repeat the process. The last line is assembled without extra spaces between words but with spaces at the end, if necessary, to meet the maxWidth requirement.

JavaScript Solution

1
2javascript
3function fullJustify(words, maxWidth) {
4    let res = [], cur = [], numOfLetters = 0
5    words.forEach(w => {
6        if(numOfLetters + w.length + cur.length > maxWidth) {
7            for(let i = 0; i < maxWidth - numOfLetters; i++){
8                cur[i%(cur.length-1 || 1)] += ' ';
9            }
10            res.push(cur.join(''));
11            cur = [], numOfLetters = 0;
12        }
13        cur.push(w);
14        numOfLetters += w.length;
15    });
16    res.push(cur.join(' ') + ' '.repeat(maxWidth - numOfLetters - cur.length + 1));
17    return res
18}

The JavaScript solution follows almost the same principles as the Python solution with slight differences due to language syntax. A for and a forEach loop are used for iteration over the words and the spaces.

While distributing extra spaces between words, the remainder (%) operator is used to add a space to every word until all the spaces are consumed.

In JavaScript, adding spaces between words or at the end of the line is done using repeat() function, which makes the code cleaner.

Java Solution

1
2java
3public List<String> fullJustify(String[] words, int maxWidth) {
4    List<String> result = new ArrayList<>();
5    int index = 0;
6    while (index < words.length) {
7        int count = words[index].length();
8        int last = index + 1;
9        while (last < words.length) {
10            if (words[last].length() + count + 1 > maxWidth) break;
11            count += words[last].length() + 1;
12            last++;
13        }
14        StringBuilder builder = new StringBuilder();
15        builder.append(words[index]);
16        int diff = last - index - 1;
17        if (last == words.length || diff == 0) {
18            for (int i = index + 1; i < last; i++) {
19                builder.append(" ");
20                builder.append(words[i]);
21            }
22            for (int i = builder.length(); i < maxWidth; i++) {
23                builder.append(" ");
24            }
25        } else {
26            int spaces = (maxWidth - count) / diff;
27            int r = (maxWidth - count) % diff;
28            for (int i = index + 1; i < last; i++) {
29                for (int k = spaces; k > 0; k--) {
30                    builder.append(" ");
31                }
32                if(r > 0) {
33                    builder.append(" ");
34                    r--;
35                }
36                builder.append(" ");
37                builder.append(words[i]);
38            }
39        }
40        result.add(builder.toString());
41        index = last;
42    }
43    return result;
44}

This Java solution calculates the length of characters for the words to be added in a line and then appends spaces in between accordingly. StringBuilder is used for efficient string concatenation. The spaces are appended by looping through the minimum required spaces between words and extra remaining spaces based on the modulus operation. If a line contains only a single word or it is the last line, then the space padding will be added to the right.

For all these solutions, the time complexity is O(n), where n is the number of words, because we need to go through each word once. The space complexity is also O(n) as we store the justified lines in an array or list.