68. Text Justification

Array
String
Simulation
Greedy

TIME

O(total characters)

SPACE

O(maxWidth) excluding the output

Intuition

Two independent jobs: deciding which words share a line, and spacing a line once its words are fixed. Keeping them separate is what stops this from turning into tangled index arithmetic.

Packing is greedy and the problem says so: keep adding words while they fit. The fit test has to account for the minimum single space before each added word, so a line holding k words of total length L occupies L + (k - 1) characters at its tightest. Written incrementally, the next word fits when currentLen + k + wordLen <= maxWidth, where k is the count already on the line.

Spacing splits into two shapes:

A normal line with at least two words spreads maxWidth - totalWordLen spaces over k - 1 gaps. Integer division gives the base gap width, and the remainder is handed out one extra space at a time starting from the left, which is exactly the "left slots get more" rule.
A line that cannot be spread gets single spaces and right padding. That covers two distinct cases which behave identically: the last line, and any line holding a single word (no gaps exist to absorb the padding).

Missing that single-word case is the usual bug here; Example 2's "acknowledgment " is a middle line, not the last one, yet it is still left-justified.

Approach

Walk the words, accumulating a current line and its running word-length total.
Before adding word, test currentLen + len(line) + len(word) <= maxWidth. If it fails, flush the line and start a new one with word.
Flushing a fully justified line (2+ words, not the last):
- spaces = maxWidth - currentLen, gaps = len(line) - 1
- base, extra = divmod(spaces, gaps)
- Join, giving the first extra gaps base + 1 spaces and the rest base.
Flushing a left-justified line (last line, or a single word):
- " ".join(line) then right-pad with spaces to maxWidth.
Return the collected lines.

Complexity

Time: O(total characters), each word is examined once and copied into one line
Space: O(maxWidth) of working buffer, plus the output

Edge Cases

Single-word line in the middle of the text is left-justified, not stretched (Example 2)
Last line is always left-justified even when it holds several words
A word exactly maxWidth long occupies its own line
One word total → a single left-justified, right-padded line
Every returned line must measure exactly maxWidth, including the padded ones
The remainder distribution goes left-to-right; reversing it produces Example 1's spacing incorrectly

Code

from typing import List


class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        """
        68. Text Justification
        Time: O(total characters)
        Space: O(maxWidth) excluding the output
        """
        result = []
        line = []          # words on the current line
        line_len = 0       # total word length, excluding spaces

        def flush(words_on_line: List[str], total: int, last: bool) -> str:
            if last or len(words_on_line) == 1:
                # last line and single-word lines are left-justified
                text = " ".join(words_on_line)
                return text + " " * (maxWidth - len(text))

            gaps = len(words_on_line) - 1
            base, extra = divmod(maxWidth - total, gaps)
            parts = []
            for i, w in enumerate(words_on_line[:-1]):
                # the leftmost `extra` gaps take one additional space
                parts.append(w)
                parts.append(" " * (base + (1 if i < extra else 0)))
            parts.append(words_on_line[-1])
            return "".join(parts)

        for word in words:
            # len(line) accounts for one mandatory space before each new word
            if line and line_len + len(line) + len(word) > maxWidth:
                result.append(flush(line, line_len, last=False))
                line, line_len = [], 0
            line.append(word)
            line_len += len(word)

        result.append(flush(line, line_len, last=True))
        return result

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

/**
 * 68. Text Justification
 * Time: O(total characters)
 * Space: O(maxWidth) excluding the output
 */
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        List<String> line = new ArrayList<>(); // words on the current line
        int lineLen = 0;                       // total word length, excluding spaces

        for (String word : words) {
            // line.size() accounts for one mandatory space before each new word
            if (!line.isEmpty() && lineLen + line.size() + word.length() > maxWidth) {
                result.add(flush(line, lineLen, maxWidth, false));
                line.clear();
                lineLen = 0;
            }
            line.add(word);
            lineLen += word.length();
        }

        result.add(flush(line, lineLen, maxWidth, true));
        return result;
    }

    private String flush(List<String> words, int total, int maxWidth, boolean last) {
        StringBuilder sb = new StringBuilder();

        if (last || words.size() == 1) {
            // last line and single-word lines are left-justified
            for (int i = 0; i < words.size(); i++) {
                if (i > 0) {
                    sb.append(' ');
                }
                sb.append(words.get(i));
            }
            while (sb.length() < maxWidth) {
                sb.append(' ');
            }
            return sb.toString();
        }

        int gaps = words.size() - 1;
        int base = (maxWidth - total) / gaps;
        int extra = (maxWidth - total) % gaps;
        for (int i = 0; i < words.size() - 1; i++) {
            sb.append(words.get(i));
            // the leftmost `extra` gaps take one additional space
            int width = base + (i < extra ? 1 : 0);
            for (int s = 0; s < width; s++) {
                sb.append(' ');
            }
        }
        sb.append(words.get(words.size() - 1));
        return sb.toString();
    }
}