Run-Length Encoding (Compress and Expand Runs)

Run-length encoding (RLE) stores counts of consecutive identical characters—aaab→a3b1 depending on format. Decoding walks counts; encoding scans with a run accumulator.

Why this shows up in the real world

Fax and early bitmap compression used RLE on long runs of white pixels. Interview problems love compact string expansions with nested multipliers.

Core idea (explained for students)

Encode: track (ch, count) pairs. Decode: repeat ch * int(k) from a parsed token stream—watch for multi-digit counts.

Try this in Python

def rle_encode(s: str) -> str:
    if not s:
        return ""
    parts, ch, k = [], s[0], 1
    for c in s[1:]:
        if c == ch:
            k += 1
        else:
            parts.append(f"{ch}{k}")
            ch, k = c, 1
    parts.append(f"{ch}{k}")
    return "".join(parts)


print(rle_encode("aaabcca"))

Common mistakes

• Ambiguous formats mixing digits into alphabet—define escaping or length prefixes.
• Exploding decoded size—validate caps before materializing.

Key takeaways

• Specify token grammar (digits always counts vs alternating) before coding.
• For huge outputs, stream results instead of one giant string.