65. Text Justification

Greedily fit as many words as possible on each line, then distribute the leftover spaces as evenly as possible between the gaps (left gaps get the extra when it doesn't divide evenly). The last line — and any single-word line — is left-justified.

Idea

Build lines greedily: keep adding words while the current word lengths plus one space between each still fit in maxWidth. Once a word doesn't fit, justify the completed line:

• If it has one word (or it's the last line): left-justify and pad the right with spaces.
• Otherwise distribute maxWidth - total_word_length spaces across the gaps = wordCount - 1 slots: each gets spaces // gaps, and the leftmost spaces % gaps gaps get one extra.

Algorithm

1. Accumulate words into line while line_len + len(line) + len(word) <= maxWidth.
2. When the next word overflows, justify line (even spacing) and reset.
3. After the loop, left-justify the final line.

Worked example: words = ["This","is","an",...], maxWidth = 16

First line packs This is an → distribute 6 spaces over 2 gaps → "This is an".

Complexity

• Time: O(total characters).
• Space: O(total characters) for the output.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        List<String> line = new ArrayList<>();
        int lineLen = 0;
        for (String w : words) {
            if (lineLen + line.size() + w.length() > maxWidth) {
                int spaces = maxWidth - lineLen;
                StringBuilder sb = new StringBuilder();
                if (line.size() == 1) {
                    sb.append(line.get(0));
                    for (int s = 0; s < spaces; s++) {
                        sb.append(' ');
                    }
                } else {
                    int gaps = line.size() - 1;
                    int even = spaces / gaps;
                    int extra = spaces % gaps;
                    for (int i = 0; i < line.size(); i++) {
                        sb.append(line.get(i));
                        if (i < gaps) {
                            int pad = even + (i < extra ? 1 : 0);
                            for (int s = 0; s < pad; s++) {
                                sb.append(' ');
                            }
                        }
                    }
                }
                result.add(sb.toString());
                line = new ArrayList<>();
                lineLen = 0;
            }
            line.add(w);
            lineLen += w.length();
        }
        StringBuilder last = new StringBuilder(String.join(" ", line));
        while (last.length() < maxWidth) {
            last.append(' ');
        }
        result.add(last.toString());
        return result;
    }
}