Decode a run-length string

Question

Reverse run-length encoding: given a string that is a sequence of <character><count> pairs, rebuild the original text. Counts can be more than one digit.

"a2b1c5a3"  ->  "aabcccccaaa"
"x12"       ->  "xxxxxxxxxxxx"     # twelve x's
""          ->  ""

Return the decoded string in $O(\text{output length})$ time. Assume characters are letters and each is followed by a count of at least 1.

Accepted Answer

Walk the string with an index. Read one character, then scan forward over all consecutive digits to read the full (possibly multi-digit) count, and append that character repeated. The multi-digit case is the trap: reading only one digit turns "x12" into "x" then a stray "12". Build a list of parts and join once, since repeated string concatenation is O(n^2). Tracing "a2b1c5a3": read a count 2 gives "aa", then b1 gives "b", c5 gives "ccccc", a3 gives "aaa". Joined, that is "aabcccccaaa". For "x12" the digit scan captures 12, producing twelve xs. Time O(	ext{output length}), space O(	ext{outp…

Decode a run-length string

Your answer

More Coding questions