String Parsing and Compression

In this topic we process strings by hand: we compress, evaluate expressions, check brackets and learn the cost of building a string. All of it follows one scheme: a pass over the string with a little state, so time is O(n). The previous topic: palindromes and anagrams.

Run-length encoding (RLE)

A run is a block of equal consecutive characters. RLE replaces each run with character + count. The algorithm: compare s[i] with s[i - 1], increase the counter, and write the run to the result when it ends. The last run is written after the loop. Time O(n), memory O(n). It wins on long runs ("a" * 100 → a100) and loses on single characters (abc → a1b1c1, twice as long).

def rle_encode(s):
    if not s:
        return ""
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    out.append(s[-1] + str(count))
    return "".join(out)

import re

def rle_decode(t):
    return "".join(ch * int(n) for ch, n in re.findall(r"(\D)(\d+)", t))