008. Run-Length Encoding

Why this mechanism works

A run's final count becomes known when a different character arrives. Keep one uncommitted run and append it at that boundary. The final run has no following character to trigger the boundary, so termination must explicitly flush it. This is a commit-point problem rather than a frequency-counting problem.

State and boundaries

symbol and count describe the active run. output contains only completed runs, in order.

Protocol

1. Handle empty input.
2. Start the first run.
3. Extend while the incoming character matches.
4. On change append the old run and start the new one.
5. Append the final run after the loop.

Visualization

aaa | bb | c
(a,3) (b,2) (c,1)
change commits; end flushes

Python implementation

def run_length_encode(text):
    if not text:
        return []
    output = []
    symbol, count = text[0], 1
    for i in range(1, len(text)):
        char = text[i]
        if char == symbol:
            count += 1
        else:
            output.append((symbol, count))
            symbol, count = char, 1
    output.append((symbol, count))
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 run_length_encode: if not text:
text='aaabbc'

L4 run_length_encode: output = []
text='aaabbc'; output=[]

L5 run_length_encode: symbol, count = text[0], 1
text='aaabbc'; output=[]; symbol='a'; count=1

L6 run_length_encode: for i in range(1, len(text)):
text='aaabbc'; output=[]; symbol='a'; count=1; i=1

L7 run_length_encode: char = text[i]
text='aaabbc'; output=[]; symbol='a'; count=1; i=1; char='a'

L9 run_length_encode: count += 1
text='aaabbc'; output=[]; symbol='a'; count=2; i=1; char='a'

L6 run_length_encode: for i in range(1, len(text)):
text='aaabbc'; output=[]; symbol='a'; count=2; i=2; char='a'

L9 run_length_encode: count += 1
text='aaabbc'; output=[]; symbol='a'; count=3; i=2; char='a'

... 7 intermediate state changes omitted ...

L7 run_length_encode: char = text[i]
text='aaabbc'; output=[('a', 3)]; symbol='b'; count=2; i=5; char='c'

L11 run_length_encode: output.append((symbol, count))
text='aaabbc'; output=[('a', 3), ('b', 2)]; symbol='b'; count=2; i=5; char='c'

L12 run_length_encode: symbol, count = char, 1
text='aaabbc'; output=[('a', 3), ('b', 2)]; symbol='c'; count=1; i=5; char='c'

L13 run_length_encode: output.append((symbol, count))
text='aaabbc'; output=[('a', 3), ('b', 2), ('c', 1)]; symbol='c'; count=1; i=5; char='c'

L2 run_length_encode: if not text:
text=''

Why the solution is correct

Each matching event stays within the active maximal run. A change proves the old run is complete and starts the next run at count one. The final flush accounts for the only run that lacks a following boundary. Every input character belongs to one output tuple.

Time and space

O(n) time; O(r) output space for r runs and O(1) other state.

Common mistakes

A frequency map merges nonadjacent runs. Forgetting the final append loses the entire result for a one-run string.

Reasoning card

Transfer exercise

Decode the tuples back to the original string and use that identity as a property test.