Problem Description

The Text Justification problem asks you to arrange a list of words into lines of text, so that each line has exactly maxWidth characters. Words should be packed greedily, meaning as many as possible in a line, with at least one space between words. Extra spaces should be distributed as evenly as possible between the words; if the number of spaces does not divide evenly, the leftmost slots get more spaces. The last line should be left-justified, and no extra space is inserted between words.

• Each word is a string of non-space characters.
• Each line must have exactly maxWidth characters.
• Spaces are only inserted between words, not at the start or end of a line.
• For the last line, words are left-justified and extra spaces are added at the end.
• There is only one valid solution for each input.
• No word is split between lines.

Thought Process

To solve this problem, start by thinking about how you naturally write text: you fill a line with as many words as will fit, then move to the next line. The challenge here is to distribute spaces so each line is exactly maxWidth characters, and to handle the last line differently (left-justified).

A brute-force solution could try every possible way to split the words into lines and pick the one that fits the constraints. However, this is inefficient and unnecessary, since the problem allows us to pack greedily: always fill the next line with as many words as possible.

The main complexity comes from distributing spaces: for lines with more than one word, you must calculate how many spaces go between each word and ensure the total length matches maxWidth. For the last line or lines with only one word, you left-justify.

Solution Approach

Here’s how to approach the problem step by step:

1. Group words into lines:
   • Start with an empty line and add words one by one, as long as the total length plus spaces does not exceed maxWidth.
   • When a word would make the line too long, process the current line and start a new one.
2. Justify each line:
   • If it’s the last line or the line has only one word, left-justify: join words with a single space, and pad spaces at the end to reach maxWidth.
   • Otherwise, distribute spaces evenly:
     • Calculate total spaces needed: maxWidth - sum(length of words).
     • Divide spaces among the gaps between words. If spaces don’t divide evenly, add one extra space to the leftmost gaps.
3. Repeat until all words are processed.

This approach ensures that each line is filled greedily and justified according to the rules. We use simple arrays and string operations, making the algorithm efficient and easy to understand.

Example Walkthrough

Consider words = ["This", "is", "an", "example", "of", "text", "justification."] and maxWidth = 16.

1. Start with an empty line. Add "This" (length 4), then "is" (length 2 + 1 space = 7), then "an" (length 2 + 2 spaces = 10), then "example" (length 7 + 3 spaces = 17). This exceeds maxWidth, so stop at "an".
2. The first line is ["This", "is", "an"]. Total length of words = 4 + 2 + 2 = 8. Spaces to distribute = 16 - 8 = 8. There are 2 gaps, so each gets 4 spaces.
   Line: "This is an"
3. Start new line with "example" (7), then "of" (2 + 1 space = 10), then "text" (4 + 2 spaces = 15), then "justification." (14 + 3 spaces = 18). Exceeds maxWidth, so stop at "text".
4. Second line: ["example", "of", "text"]. Length = 7 + 2 + 4 = 13. Spaces = 16 - 13 = 3. Two gaps, so first gets 2 spaces, second gets 1.
   Line: "example of text"
5. Last line: ["justification."]. Only one word, so left-justify and pad spaces at end.
   Line: "justification. "

Final output:

• "This is an"
• "example of text"
• "justification. "

Time and Space Complexity

Brute-force approach: Would involve trying all possible ways to split words into lines, which is exponential in the number of words (O(2^n)), and not feasible.

Optimized greedy approach (our solution):

• Time Complexity: O(n), where n is the total number of words. We process each word once, and string operations per line are bounded by maxWidth.
• Space Complexity: O(n * k), where k is the average word length, since we store the output lines.

The space for the result is proportional to the input size, and we use only a few extra variables.

Summary

The Text Justification problem is a classic string formatting challenge. By grouping words greedily and carefully distributing spaces, we can efficiently build justified text lines that meet all constraints. The key insight is to handle space distribution precisely and treat the last line as a special case. This approach is both efficient and elegant, making use of simple data structures and clear logic.

Code Implementation

class Solution:
    def fullJustify(self, words, maxWidth):
        res = []
        curr = []
        num_of_letters = 0
        for word in words:
            if num_of_letters + len(word) + len(curr) > maxWidth:
                for i in range(maxWidth - num_of_letters):
                    curr[i % (len(curr)-1 or 1)] += ' '
                res.append(''.join(curr))
                curr, num_of_letters = [], 0
            curr.append(word)
            num_of_letters += len(word)
        res.append(' '.join(curr).ljust(maxWidth))
        return res
      

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res, curr;
        int num_of_letters = 0;
        for (auto& word : words) {
            if (num_of_letters + word.size() + curr.size() > maxWidth) {
                for (int i = 0; i < maxWidth - num_of_letters; ++i)
                    curr[i % (curr.size() - 1 ? curr.size()-1 : 1)] += " ";
                string line;
                for (auto& w : curr) line += w;
                res.push_back(line);
                curr.clear();
                num_of_letters = 0;
            }
            curr.push_back(word);
            num_of_letters += word.size();
        }
        string last = "";
        for (int i = 0; i < curr.size(); ++i) {
            last += curr[i];
            if (i != curr.size()-1) last += " ";
        }
        last += string(maxWidth - last.size(), ' ');
        res.push_back(last);
        return res;
    }
};
      

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        List<String> curr = new ArrayList<>();
        int num_of_letters = 0;
        for (String word : words) {
            if (num_of_letters + word.length() + curr.size() > maxWidth) {
                for (int i = 0; i < maxWidth - num_of_letters; ++i) {
                    curr.set(i % (curr.size() - 1 == 0 ? 1 : curr.size() - 1), curr.get(i % (curr.size() - 1 == 0 ? 1 : curr.size() - 1)) + " ");
                }
                StringBuilder line = new StringBuilder();
                for (String w : curr) line.append(w);
                res.add(line.toString());
                curr = new ArrayList<>();
                num_of_letters = 0;
            }
            curr.add(word);
            num_of_letters += word.length();
        }
        StringBuilder last = new StringBuilder();
        for (int i = 0; i < curr.size(); ++i) {
            last.append(curr.get(i));
            if (i != curr.size()-1) last.append(" ");
        }
        while (last.length() < maxWidth) last.append(" ");
        res.add(last.toString());
        return res;
    }
}
      

var fullJustify = function(words, maxWidth) {
    let res = [];
    let curr = [];
    let num_of_letters = 0;
    for (let word of words) {
        if (num_of_letters + word.length + curr.length > maxWidth) {
            for (let i = 0; i < maxWidth - num_of_letters; ++i) {
                curr[i % (curr.length - 1 || 1)] += ' ';
            }
            res.push(curr.join(''));
            curr = [];
            num_of_letters = 0;
        }
        curr.push(word);
        num_of_letters += word.length;
    }
    let last = curr.join(' ');
    last += ' '.repeat(maxWidth - last.length);
    res.push(last);
    return res;
};