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, so you cannot build a separate output string.

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 main 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. The logic is correct, but it uses O(n) auxiliary space.

from typing import List

def compress(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. The runtime is fine, but the auxiliary list violates the problem’s explicit O(1)-space requirement.

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

The key fact is that 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 becomes 2 chars, 10–99 becomes 3 chars, and so on), while a run of 1 stays 1 character. So a write pointer can overwrite the array behind a read pointer that has already consumed the run, and write can never overtake read.

from typing import List

def compress(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 for in-place rewriting: read consumes input tokens (here, whole runs) and write emits output tokens. It is safe in place because each emitted token is no longer than the input it replaces. Whenever a rewrite provably never expands the data, you can stream output over input in a single pass. State that size inequality explicitly in an interview, since it is what justifies the approach.