UIREADY.dev
Run-Length EncodingLoading saved progress…

Run-Length Encoding

Run-length encoding (RLE) is a simple lossless compression scheme that replaces each run of one repeated character with a count followed by that character, so aaab becomes 3a1b. It shines on data with long stretches of the same value — scanned faxes, simple bitmaps, sensor logs — and is a classic warm-up because the encode and decode halves are short but full of small traps. You will implement both, packaged on one object as runLengthEncoding = { encode, decode }. See run-length encoding for background.

Signature

runLengthEncoding.encode(str)  // -> compressed string, e.g. '3a2b1c'
runLengthEncoding.decode(str)  // -> original string; the exact inverse of encode

Each run in the output is written as a count immediately followed by its character — for example 3a for three as. The count is always present, even when it is 1.

Examples

runLengthEncoding.encode('aaabbc');          // '3a2b1c'
runLengthEncoding.encode('wwwwaaadexxxxxx');  // '4w3a1d1e6x'
runLengthEncoding.encode('');                // ''

runLengthEncoding.decode('3a2b1c');          // 'aaabbc'
runLengthEncoding.decode('12a3b');           // 'aaaaaaaaaaaabbb'  (12 a's, then 3 b's)
runLengthEncoding.decode(runLengthEncoding.encode('mississippi')); // 'mississippi'

Notes

  • Format — every run is a count then its character, and the count is emitted even for a single character, so abc encodes to 1a1b1c. Writing the count always keeps decode a simple alternating read.
  • Multi-digit counts — a run of ten or more needs a multi-digit count: a run of twelve as encodes to 12a. On decode you must read the whole number before the character, not just the first digit.
  • Runs reset on a new character — count only consecutive repeats. aabaa is three runs, 2a1b2a, not a merged pair of a runs.
  • Empty string — encode('') and decode('') are both ''.
  • No digits in the input — this simple format assumes the input has no digits, because a digit in the input is indistinguishable from a count on decode. Handling arbitrary data needs escaping — out of scope here.
  • Round-trip — decode(encode(s)) must equal s for every digit-free string s. Build both functions yourself; no libraries.

FAQ

Why does decode have to read the whole number instead of one digit?
A run can be ten or more characters long, so its count needs more than one digit — a run of twelve encodes to 12x. If decode reads only a single digit it takes 1 as the count and 2 as the character, which is wrong. It must consume every consecutive digit before reading the character that follows.
Why emit a count of 1 for a single character?
Writing 1a instead of just a keeps the format uniform: every character in the output is preceded by a number. That makes decoding unambiguous — the decoder always reads a count then a character. The variant that omits the 1 saves space but needs a smarter decoder.
What happens if the input already contains digits?
This simple format assumes the input has no digits, because a digit in the input is indistinguishable from a count on decode. To encode arbitrary data you need an escaping scheme or a length-prefix format, which the solution describes under going further.
Loading editor…