Measure each run
Shorten a string by writing each run of a letter once, with its length. About 8 minutes.
Send a scout ahead
"aaabcc" can be written shorter as "a3bc2": each run of repeated letters becomes the letter and how many there were. Runs of just one letter stay as the letter.
Put one finger at the start of a run. Send a second finger, a scout, forward as long as it sees the same letter. When the scout stops, the gap between the two fingers is the length of the run.
- out
- ""
i marks where a run starts. The scout starts there too.
Jump to where the scout stopped
The next run starts exactly where the scout stopped, so move the first finger there and send the scout off again. Every letter is looked at once, and the whole string is done in one walk.
Remember the special case: a run of length 1 is written as just the letter, with no 1 after it.
out = []
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
out.append(s[i])
if j - i > 1:
out.append(str(j - i))
i = j
return "".join(out)How does "aaabcc" compress?
- Aa3bc2
- Ba3b1c2
- Ca3c2b
Show the answer
a3bc2. Runs of 3 a's, 1 b and 2 c's; the single b is written alone.
Compress runs
You get a string of lowercase letters. Replace every run of the same letter by the letter followed by the run's length, but write runs of length 1 as just the letter. Return the result.
s = "aaabcc" → "a3bc2"
0 ≤ length ≤ 100,000 · only a to z