Run-length compress a fill sequence

Question

A stream of fill side markers like "BBBSS" (buy, buy, buy, sell, sell) is wordy. Compress it by replacing each run of identical characters with the character followed by the run length. Return the run-length encoding of the string. Aim for O(n).

Accepted Answer

Scan left to right tracking the current character and how long its run has lasted. When a different character appears, flush the current character and its count to the output, then reset. Flush once more at the end for the final run. Tracing "BBBSS": three Bs accumulate to run = 3, flushed as "B3" when the first S arrives; the two Ss flush at the end as "S2", giving "B3S2". Time O(n), space O(n) for the output. Edge cases: an empty input returns "", and a single character becomes "X1". Note that for input with no repeats this "compression" grows the string, real codecs fall back to the raw fo…

Run-length compress a fill sequence

Your answer

More Coding questions