String Compression

Problem

You are given a list of characters chars. Compress it in place using run-length encoding: replace each maximal run of a repeated character with the character followed by the run’s length — except that runs of length 1 get no number. Lengths of 10 or more are written as their individual digit characters (e.g. a run of 12 as becomes 'a', '1', '2').

Overwrite the front of chars with the compressed sequence and return its length. Use O(1) extra space — building a separate string is against the rules.

Examples

Example 1

Input:  chars = ["a","a","b","b","c","c","c"]
Output: 6, chars = ["a","2","b","2","c","3", ...]

Runs aa, bb, ccc become a2, b2, c3.

Example 2

Input:  chars = ["a"]
Output: 1, chars = ["a"]

A single character gets no count.

Example 3

Input:  chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: 4, chars = ["a","b","1","2", ...]

a alone, then twelve bs → b followed by digits '1', '2'.

Constraints

• 1 <= chars.length <= 2000
• chars[i] is a lowercase/uppercase letter, digit, or symbol.
• Must run in O(n) time and O(1) extra space — the in-place overwrite is the entire difficulty.

Think about it first

TL;DR

Read/write two pointers, one pass of run-length encoding in place — O(n) time, O(1) extra space.

Approach 1 — Brute force (build the output separately)

Scan the runs and append to a fresh list, then copy back. This is the right logic with the wrong memory.

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        out: List[str] = []
        i = 0
        n = len(chars)
        while i < n:
            j = i
            while j < n and chars[j] == chars[i]:
                j += 1
            out.append(chars[i])
            run = j - i
            if run > 1:
                out.extend(str(run))
            i = j
        chars[: len(out)] = out
        return len(out)

Complexity: O(n) time, O(n) space. Time is fine; the auxiliary list violates the problem’s explicit O(1)-space requirement — that constraint, not speed, is what kills this version.

Approach 2 — In-place two pointers (read runs, write compressed)

The insight: the compressed form of any run never exceeds the run itself — a run of length L ≥ 2 becomes 1 + digits(L) characters, and 1 + digits(L) ≤ L for every L ≥ 2 (a run of 2 → 2 chars, 10–99 → 3 chars, etc.), while a run of 1 stays 1 character. Therefore a write pointer can safely overwrite the array behind a read pointer that has already consumed the run: write can never overtake read.

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0
        read = 0
        n = len(chars)
        while read < n:
            ch = chars[read]
            run_start = read
            while read < n and chars[read] == ch:
                read += 1
            run = read - run_start

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

Walkthrough on chars = ["a","a","b","b","c","c","c"]:

Returns 6. ✓

And on chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] (one a, twelve bs):

1. Run a, length 1 → write a only (no count). write = 1.
2. Run b, length 12 → write b, then digits '1', '2'. write = 4.

Prefix ["a","b","1","2"], returns 4. ✓

Complexity: O(n) time — read visits each character once, write trails it. O(1) extra space (the str(run) temporary is at most 4 characters since n ≤ 2000).

Common pitfalls

• Writing "1" for singleton runs: runs of length 1 must emit the character alone; blindly appending the count is the most common wrong answer.
• Multi-digit counts as one token: a run of 12 must become the two characters '1', '2' — writing the string "12" into a single cell type-checks in Python but is wrong.
• Losing the run boundary: capture the run’s character before advancing read, or the comparison target shifts mid-run.
• Returning the array or forgetting that cells past write are garbage: the judge reads exactly chars[:write]; you don’t need to clean up the tail, but you must return write.

Pattern takeaway

This is the read/write two-pointer pattern in its “transducer” form: read consumes input tokens (here, whole runs), write emits output tokens, and the whole thing is safe in place because of a one-line size argument — each emitted token is no longer than the input it replaces. Whenever a rewrite provably never expands, you can stream output over input in a single pass; proving that inequality is the first thing to say out loud in an interview.