Run-Length Encoding

Medium · rating 1200 · strings

Compress a string by replacing each run of a repeated character with the character followed by the run length. For example aaabbc becomes a3b2c1. Read a single line and print its run-length encoding.

Editorial

Run-Length Encoding (RLE) is a simple lossless compression scheme and a common string task: replace each run of a repeated character with the character followed by the run length (aaabb → a3b2).

Approach

Scan the string, extending the current run while characters match; when it ends, emit the character and its count, then start the next run.

out = []
i = 0
while i < len(s):
    j = i
    while j < len(s) and s[j] == s[i]: j += 1
    out.append(s[i] + str(j - i))
    i = j
return ''.join(out)

Complexity

Time: O(n). Space: O(n).

Open Run-Length Encoding in Code Arena →