Run Length Compression
Problem
Shrink a piece of text by replacing each run of identical characters with that character followed by the length of the run. A run of length one keeps the bare character with no number after it. Return the compressed text only when it is strictly shorter than the original; otherwise return the original unchanged.
Examples
Input: text = "aaabccdddd"
Output: "a3bc2d4"
Why: the lone b stays bare while the longer runs pick up a countInput: text = "abcd"
Output: "abcd"
Why: compressing would not shrink anything, so the original winsInput: text = ""
Output: ""
Why: edge case, there is no run to encodeHints
0 / 3
The text is a sequence of runs, so think in runs rather than in single characters: each run turns into at most a couple of output characters.
Use one position to mark where the current run starts and a second one to find where it ends, then jump the first position to the second.
From the start of a run, advance a scout position while it keeps seeing the same character. Emit the character, and emit the run length only when the scout travelled more than one step. Continue from the scout. At the very end, compare lengths and return whichever text is shorter.
Solution
Two positions describe the current run: one marks its start and a scout walks to its end, which makes the run length a simple subtraction. Each run contributes its character, plus a count only when the run is longer than one, so short runs are never inflated. The final length comparison honours the rule that compression must actually pay for itself. Time is O(n) because the scout never revisits a character, and space is O(n) for the built output.
def compress_runs(text):
out, i = [], 0
while i < len(text):
j = i
while j < len(text) and text[j] == text[i]:
j += 1 # walk to the end of this run
out.append(text[i])
if j - i > 1: # runs of length one stay bare
out.append(str(j - i))
i = j # continue from where the run ended
packed = "".join(out)
return packed if len(packed) < len(text) else text
print(compress_runs("aaabccdddd")) # -> a3bc2d4
print(compress_runs("abcd")) # -> abcd
print(compress_runs("")) # ->Stuck on the idea rather than the code? String Compression covers it.