Run-length string compression

Question

Implement basic run-length encoding: replace each run of a repeated character with the character followed by its count. If the "compressed" string would not be strictly shorter than the original, return the original unchanged.

"aabcccccaaa" -> "a2b1c5a3"     # 8 chars vs 11
"abc"         -> "abc"          # "a1b1c1" is longer; keep original
""            -> ""

Return the compressed (or original) string in $O(n)$ time.

Accepted Answer

Walk the string once, tracking the current run's character and length. When the character changes, flush the run to the output and reset. Flush once more after the loop, forgetting the final run is the classic bug here. Build the output as a list of parts and join at the end: repeated string concatenation in a loop is O(n^2) in the worst case because strings are immutable. Tracing "aabcccccaaa": runs are a×2, b×1, c×5, a×3, so the output is "a2b1c5a3" (length 8, beats 11). For "abc" the encoding "a1b1c1" is longer, so the original comes back. Time O(n), space O(n) for the output. Worth mentio…

Run-length string compression

Your answer

More Coding questions