Run-length encode a string: replace each maximal run of the same character with
<count><char>. Always include the count, even when it's 1.
compress(s)
This is the inverse of Uncompress.
Input format: the string to compress.
"ccaaat" // → "2c3a1t"
"abc" // → "1a1b1c"
"aaaa" // → "4a"
This is the inverse of uncompress: turn runs of repeated characters back into <count><char> groups. The central task is finding where one run ends and the next begins.
Processing one character at a time and deciding immediately whether to start a new group or extend the current one means remembering the previous character and its run length — effectively simulating a second pointer anyway. Cleaner to make that pointer explicit.
One pointer marks the start of the current run. A second scans forward as long as it matches the character at the start. The moment it hits a different character (or the string ends), the run is over — its length is the distance between the two pointers.
Append the length and character, move the start pointer to where the scan stopped, and repeat until the start pointer reaches the end.
The scanning pointer only moves forward and never revisits counted characters, and the start pointer jumps directly to where scanning stopped — every character is examined exactly once, giving time proportional to the input length.
Writing a run of length one as 1x rather than x avoids ambiguity when decompressing — otherwise you couldn't tell whether abc meant three separate runs or something else. Keeping the count explicit for every group is what makes this a clean, unambiguous inverse of uncompress.
def compress(s):
out = ""
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
out += str(j - i) + s[i]
i = j
return out
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.