# LeetCode 443: String Compression

## Problem Restatement

We are given an array of characters:

```python
chars
```

We must compress the array in-place using these rules:

| Case | Output |
|---|---|
| Single character | Keep the character only |
| Repeated character | Write character followed by count |

For example:

```python
["a","a","b","b","c","c","c"]
```

becomes:

```python
["a","2","b","2","c","3"]
```

The compressed result must be written back into the same array.

The function returns the new length after compression.

Counts larger than `9` must be split into multiple characters.

For example:

```python
12
```

must be written as:

```python
"1", "2"
```

The official problem asks for in-place compression with constant extra space. ([leetcode.com](https://leetcode.com/problems/string-compression/))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Character array `chars` |
| Output | Length of compressed array |
| Compression | Character + frequency |
| Single occurrence | No count written |
| Extra space | Must be constant |

Example function shape:

```python
def compress(chars: list[str]) -> int:
    ...
```

## Examples

Example 1:

```python
chars = ["a","a","b","b","c","c","c"]
```

Compression groups:

| Group | Result |
|---|---|
| `"aa"` | `"a2"` |
| `"bb"` | `"b2"` |
| `"ccc"` | `"c3"` |

Compressed array:

```python
["a","2","b","2","c","3"]
```

Returned length:

```python
6
```

Example 2:

```python
chars = ["a"]
```

Single characters keep only themselves.

Compressed array:

```python
["a"]
```

Returned length:

```python
1
```

Example 3:

```python
chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
```

There are:

```python
12
```

copies of `"b"`.

Compressed array becomes:

```python
["a","b","1","2"]
```

Returned length:

```python
4
```

## First Thought: Build a New String

We could create another array:

```python
result = []
```

Then append compressed groups into it.

This is simple, but the problem requires in-place modification with constant extra space.

So we must overwrite the original array directly.

## Key Insight

Compression happens group by group.

For example:

```text
a a a b b c
```

contains groups:

```text
aaa
bb
c
```

We can process each group independently.

Use two pointers:

| Pointer | Meaning |
|---|---|
| `i` | Start of current group |
| `j` | Finds the end of the group |

We also keep a write pointer:

```python
write
```

which tells where to place compressed output.

For each group:

1. Write the character.
2. Compute the group size.
3. If size > 1, write the digits of the count.

## Algorithm

Initialize:

```python
write = 0
i = 0
```

While `i < len(chars)`:

1. Find the maximal group starting at `i`.
2. Let `j` be the first index after the group.
3. Group size:

```python
count = j - i
```

4. Write the character at position `write`.
5. Increase `write`.
6. If `count > 1`:
   - Convert count to string.
   - Write each digit into the array.
7. Move:

```python
i = j
```

At the end, return `write`.

## Correctness

At every iteration, the algorithm processes exactly one maximal contiguous group of equal characters.

Suppose the current group contains:

```python
count
```

copies of character `c`.

The compression rules require:

| Condition | Written output |
|---|---|
| `count == 1` | `"c"` |
| `count > 1` | `"c"` followed by decimal digits of `count` |

The algorithm writes exactly this representation.

The write pointer always points to the next unused position in the compressed prefix of the array. Therefore, writing the compressed representation overwrites old data safely without losing unprocessed characters, because the read pointer `i` and scanning pointer `j` always stay ahead.

After processing a group, the algorithm advances `i` to the first unprocessed character.

Thus every group is compressed exactly once, and the final prefix:

```python
chars[:write]
```

contains the required compressed array.

Therefore, returning `write` gives the correct compressed length.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Every character is scanned once |
| Space | `O(1)` | Compression is written in-place |

## Implementation

```python
class Solution:
    def compress(self, chars: list[str]) -> int:
        write = 0
        i = 0
        n = len(chars)

        while i < n:
            j = i

            while j < n and chars[j] == chars[i]:
                j += 1

            count = j - i

            chars[write] = chars[i]
            write += 1

            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1

            i = j

        return write
```

## Code Explanation

We use:

```python
write = 0
```

to track where compressed output should be written.

The pointer:

```python
i = 0
```

marks the start of the current group.

For every group, we extend:

```python
j
```

while characters remain equal:

```python
while j < n and chars[j] == chars[i]:
```

Then:

```python
count = j - i
```

is the group size.

We always write the group character:

```python
chars[write] = chars[i]
write += 1
```

If the group size exceeds one:

```python
if count > 1:
```

we write every digit of the count:

```python
for digit in str(count):
```

This handles counts larger than `9`.

Finally, we move to the next group:

```python
i = j
```

At the end, `write` equals the compressed length.

## Testing

```python
def compressed(chars):
    s = Solution()
    length = s.compress(chars)
    return chars[:length]

def run_tests():
    assert compressed(
        ["a","a","b","b","c","c","c"]
    ) == ["a","2","b","2","c","3"]

    assert compressed(
        ["a"]
    ) == ["a"]

    assert compressed(
        ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
    ) == ["a","b","1","2"]

    assert compressed(
        ["a","a","a","a"]
    ) == ["a","4"]

    assert compressed(
        ["a","b","c"]
    ) == ["a","b","c"]

    assert compressed(
        ["z"] * 15
    ) == ["z","1","5"]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks multiple groups |
| Single character | Checks no count writing |
| Count `12` | Checks multi-digit counts |
| All same character | Checks one large group |
| No repeated characters | Checks unchanged compression |
| Count `15` | Checks larger multi-digit values |