# LeetCode 806: Number of Lines To Write String

## Problem Restatement

We are given a string `s` containing only lowercase English letters.

We are also given an array `widths` of length `26`, where:

```python
widths[0]  # width of 'a'
widths[1]  # width of 'b'
widths[25] # width of 'z'
```

Each line can contain at most `100` pixels.

We write the characters of `s` from left to right. For each character, if it fits on the current line, we add it there. If it would make the current line exceed `100` pixels, we start a new line and place the character on that new line.

Return:

```python
[number_of_lines, width_of_last_line]
```

The official statement asks for the total number of lines and the width of the last line after writing the whole string.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `widths`, an array of 26 letter widths, and string `s` |
| Output | `[lines, last_width]` |
| Line limit | Each line can use at most `100` pixels |
| Character set | `s` contains lowercase English letters only |

## Examples

Example 1:

```python
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
s = "abcdefghijklmnopqrstuvwxyz"
```

Every character has width `10`.

Each line can hold `10` characters because:

```python
10 * 10 = 100
```

So the lines are:

```python
abcdefghij
klmnopqrst
uvwxyz
```

The last line has `6` characters, so its width is:

```python
6 * 10 = 60
```

The answer is:

```python
[3, 60]
```

Example 2:

```python
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
s = "bbbcccdddaaa"
```

Here, `'a'` has width `4`, and every other letter has width `10`.

The first line can contain:

```python
bbbcccdddaa
```

Its width is:

```python
9 * 10 + 2 * 4 = 98
```

The last `'a'` cannot fit on the first line because:

```python
98 + 4 = 102
```

So it starts a second line.

The answer is:

```python
[2, 4]
```

## First Thought: Direct Simulation

The problem describes a process. We can simulate that process exactly.

Keep two variables:

| Variable | Meaning |
|---|---|
| `lines` | Number of lines used so far |
| `current_width` | Width used on the current line |

Start with:

```python
lines = 1
current_width = 0
```

Then process each character in `s`.

For each character, get its width. If adding it keeps the current line at most `100`, add it to the current line.

Otherwise, start a new line.

## Key Insight

There is no need for dynamic programming or backtracking.

The writing rule is greedy by definition: write as many letters as possible on the current line before moving to the next line.

So each character has only one correct place:

1. Current line, if it fits.
2. Next line, if it does not fit.

## Algorithm

For each character `ch` in `s`:

1. Convert `ch` to an index:

```python
index = ord(ch) - ord("a")
```

2. Read its width:

```python
width = widths[index]
```

3. If it fits on the current line:

```python
current_width + width <= 100
```

then add it:

```python
current_width += width
```

4. Otherwise, start a new line:

```python
lines += 1
current_width = width
```

Return:

```python
[lines, current_width]
```

## Correctness

The algorithm processes the string from left to right, exactly as required by the problem.

For each character, it checks whether placing that character on the current line would keep the line width at most `100`.

If yes, the problem rule says the character should be written on the current line, so the algorithm adds its width to `current_width`.

If no, the character cannot be written on the current line without exceeding the limit. The problem rule says writing must continue on the next line, so the algorithm increments `lines` and starts the new line with the current character.

After every character, `lines` is the number of lines used so far, and `current_width` is the width of the current last line. Therefore, after all characters are processed, returning `[lines, current_width]` gives the required result.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed once |
| Space | `O(1)` | Only two counters are stored |

The `widths` input array has fixed size `26`, so it does not affect asymptotic space.

## Implementation

```python
class Solution:
    def numberOfLines(self, widths: list[int], s: str) -> list[int]:
        lines = 1
        current_width = 0

        for ch in s:
            width = widths[ord(ch) - ord("a")]

            if current_width + width <= 100:
                current_width += width
            else:
                lines += 1
                current_width = width

        return [lines, current_width]
```

## Code Explanation

We start with one line:

```python
lines = 1
current_width = 0
```

The string is non-empty, so at least one line will be used.

For each character, we find its width:

```python
width = widths[ord(ch) - ord("a")]
```

The expression `ord(ch) - ord("a")` maps:

```python
'a' -> 0
'b' -> 1
...
'z' -> 25
```

If the character fits, we keep writing on the same line:

```python
if current_width + width <= 100:
    current_width += width
```

If it does not fit, we move to a new line:

```python
else:
    lines += 1
    current_width = width
```

The new line starts with the current character, so `current_width` becomes `width`.

Finally, return both values:

```python
return [lines, current_width]
```

## Testing

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

    assert s.numberOfLines(
        [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
        "abcdefghijklmnopqrstuvwxyz"
    ) == [3, 60]

    assert s.numberOfLines(
        [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
        "bbbcccdddaaa"
    ) == [2, 4]

    assert s.numberOfLines(
        [10] * 26,
        "abcdefghij"
    ) == [1, 100]

    assert s.numberOfLines(
        [10] * 26,
        "abcdefghija"
    ) == [2, 10]

    assert s.numberOfLines(
        [2] * 26,
        "a"
    ) == [1, 2]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| All widths `10` with alphabet | Official example with three lines |
| Mixed width with small `a` | Official example where last char wraps |
| Exactly `100` pixels | Checks boundary fits |
| `101` pixels after next char | Checks new line creation |
| Single character | Minimum string length |