# LeetCode 68: Text Justification

## Problem Restatement

We are given a list of words and an integer `maxWidth`.

We need to format the words into lines of exactly `maxWidth` characters.

The rules are:

1. Pack as many words as possible into each line.
2. Each line must have exactly `maxWidth` characters.
3. For normal lines, spaces should be distributed as evenly as possible between words.
4. If spaces cannot divide evenly, the left gaps get more spaces than the right gaps.
5. The last line is left-justified: one space between words, then trailing spaces.
6. A line with only one word is also left-justified.

Each word has length at least `1` and at most `maxWidth`, and the input contains at least one word. The official constraint allows up to `300` words.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `words` and `maxWidth` |
| Output | A list of justified lines |
| Line length | Every output line has exactly `maxWidth` characters |
| Packing rule | Put as many words as possible on each line |
| Last line | Left-justified |

Function shape:

```python
def fullJustify(words: list[str], maxWidth: int) -> list[str]:
    ...
```

## Examples

For:

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

The answer is:

```python
[
    "This    is    an",
    "example  of text",
    "justification.  ",
]
```

The first line has words:

```python
["This", "is", "an"]
```

Their total word length is:

```python
4 + 2 + 2 = 8
```

The line width is `16`, so it needs:

```python
16 - 8 = 8
```

spaces.

There are two gaps:

```text
This _ is _ an
```

So each gap gets four spaces:

```python
"This    is    an"
```

The second line has:

```python
["example", "of", "text"]
```

Total word length:

```python
7 + 2 + 4 = 13
```

Spaces needed:

```python
16 - 13 = 3
```

There are two gaps. The left gap gets two spaces, and the right gap gets one space:

```python
"example  of text"
```

The last line is left-justified:

```python
"justification.  "
```

## First Thought: Add Words One by One

The main task has two parts:

1. Decide which words belong to the current line.
2. Build that line with the correct spaces.

The first part is greedy.

We keep adding words while the line can still fit inside `maxWidth`.

When we cannot add the next word, we justify the current line and start a new one.

## Key Insight

To decide whether a word fits, we need to count both:

1. Word characters
2. Minimum spaces between words

Suppose the current line has words with total length `line_len`.

If we add another word, and the current line already has `len(line_words)` words, then we need at least one space before the new word.

So the condition is:

```python
line_len + len(line_words) + len(word) <= maxWidth
```

Here, `len(line_words)` is the number of minimum spaces needed if we add the new word.

For example, if the current line has two words, adding a third word requires two minimum gaps total.

## Space Distribution

Once a line is full, we know:

```python
total_spaces = maxWidth - total_word_length
```

If the line has more than one word, the number of gaps is:

```python
gaps = len(line_words) - 1
```

Each gap gets at least:

```python
total_spaces // gaps
```

spaces.

The leftmost gaps get one extra space while the remainder lasts:

```python
extra = total_spaces % gaps
```

So for gap index `i`:

```python
spaces = base + (1 if i < extra else 0)
```

This exactly matches the rule that left gaps receive more spaces when the spaces do not divide evenly.

## Last Line and Single-Word Lines

The last line is different.

It should have one space between words, then trailing spaces at the end.

For example:

```python
["shall", "be"]
```

with `maxWidth = 16` becomes:

```python
"shall be        "
```

A single-word line follows the same left-justified rule:

```python
"acknowledgment  "
```

So we can handle both cases with:

```python
line = " ".join(line_words)
line += " " * (maxWidth - len(line))
```

## Algorithm

Maintain:

```python
ans = []
line_words = []
line_len = 0
```

For each word:

1. If the word fits in the current line, add it.
2. Otherwise, justify the current line and append it to `ans`.
3. Start a new line with the current word.

After processing all words, left-justify the last line and append it.

Return `ans`.

## Correctness

The algorithm greedily adds a word to the current line exactly when the current words, the new word, and the minimum required spaces can fit inside `maxWidth`. Therefore each line contains as many words as possible before moving to the next line.

For every non-last line with multiple words, the algorithm computes the total number of spaces needed to make the line length exactly `maxWidth`. It divides those spaces across the gaps using quotient and remainder. Every gap receives either `base` or `base + 1` spaces, so the distribution is as even as possible. Since the extra one-space gaps are assigned from left to right, left gaps receive more spaces when needed.

For a last line or a single-word line, the algorithm joins words with one space and pads the remaining width at the end. This matches the left-justification rule.

Every input word is added to exactly one line, and every output line is padded to exactly `maxWidth`. Therefore the returned list satisfies all problem requirements.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(total characters)` | Each word and output character is processed a constant number of times |
| Space | `O(total characters)` | The output stores the justified text |

Auxiliary working space, excluding the output, is `O(maxWidth)` for the current line.

## Implementation

```python
class Solution:
    def fullJustify(
        self,
        words: list[str],
        maxWidth: int,
    ) -> list[str]:

        ans = []
        line_words = []
        line_len = 0

        def justify(words_in_line: list[str], words_len: int) -> str:
            if len(words_in_line) == 1:
                line = words_in_line[0]
                return line + " " * (maxWidth - len(line))

            total_spaces = maxWidth - words_len
            gaps = len(words_in_line) - 1

            base = total_spaces // gaps
            extra = total_spaces % gaps

            parts = []

            for i in range(gaps):
                parts.append(words_in_line[i])

                spaces = base
                if i < extra:
                    spaces += 1

                parts.append(" " * spaces)

            parts.append(words_in_line[-1])

            return "".join(parts)

        for word in words:
            if line_len + len(line_words) + len(word) <= maxWidth:
                line_words.append(word)
                line_len += len(word)

            else:
                ans.append(justify(line_words, line_len))

                line_words = [word]
                line_len = len(word)

        last_line = " ".join(line_words)
        last_line += " " * (maxWidth - len(last_line))
        ans.append(last_line)

        return ans
```

## Code Explanation

We keep the output and the current line state:

```python
ans = []
line_words = []
line_len = 0
```

`line_len` stores only the total length of words, not spaces.

The helper function formats a completed non-last line:

```python
def justify(words_in_line: list[str], words_len: int) -> str:
```

If there is only one word, pad spaces at the end:

```python
if len(words_in_line) == 1:
    line = words_in_line[0]
    return line + " " * (maxWidth - len(line))
```

Otherwise, compute spaces:

```python
total_spaces = maxWidth - words_len
gaps = len(words_in_line) - 1
```

Divide them evenly:

```python
base = total_spaces // gaps
extra = total_spaces % gaps
```

Build the line from left to right:

```python
for i in range(gaps):
    parts.append(words_in_line[i])

    spaces = base
    if i < extra:
        spaces += 1

    parts.append(" " * spaces)
```

Then append the final word:

```python
parts.append(words_in_line[-1])
```

The main loop packs words greedily:

```python
if line_len + len(line_words) + len(word) <= maxWidth:
```

If the word does not fit, justify the current line:

```python
ans.append(justify(line_words, line_len))
```

Then start a new line:

```python
line_words = [word]
line_len = len(word)
```

After all words are processed, the remaining line is the last line, so it is left-justified:

```python
last_line = " ".join(line_words)
last_line += " " * (maxWidth - len(last_line))
ans.append(last_line)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.fullJustify(
        ["This", "is", "an", "example", "of", "text", "justification."],
        16,
    ) == [
        "This    is    an",
        "example  of text",
        "justification.  ",
    ]

    assert s.fullJustify(
        ["What", "must", "be", "acknowledgment", "shall", "be"],
        16,
    ) == [
        "What   must   be",
        "acknowledgment  ",
        "shall be        ",
    ]

    assert s.fullJustify(
        ["Science", "is", "what", "we", "understand", "well",
         "enough", "to", "explain", "to", "a", "computer.",
         "Art", "is", "everything", "else", "we", "do"],
        20,
    ) == [
        "Science  is  what we",
        "understand      well",
        "enough to explain to",
        "a  computer.  Art is",
        "everything  else  we",
        "do                  ",
    ]

    assert s.fullJustify(["a"], 1) == ["a"]

    assert s.fullJustify(["a"], 3) == ["a  "]

    assert s.fullJustify(["a", "b", "c"], 3) == [
        "a b",
        "c  ",
    ]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard `maxWidth = 16` example | Checks normal space distribution |
| Single-word middle line | Checks left-justified single-word line |
| Larger paragraph | Checks uneven spacing and last line |
| `["a"]`, width `1` | Smallest exact line |
| `["a"]`, width `3` | Single word with padding |
| `["a","b","c"]`, width `3` | Greedy packing plus last-line padding |