Run it
The list-and-join version against the += version, timed on a long input so the quadratic is visible, plus the in-place variant on a character array.
The solution
O(n) time, O(1) extra space.
Two mechanisms carry it:
The inner while consumes an entire run and counts it. Both pointers advance independently, and read always stays ahead of write — which is why writing in place cannot clobber unread input.
for digit in str(count) handles counts of any size. Writing chars[write] = str(count) puts a multi-character string into one slot, which is the bug for runs longer than nine.
Why in-place is safe
The natural worry is that writing over the array destroys data still to be read. It does not, and the reason is worth stating.
For a run of length L, the output is 1 + digits(L) characters. That is at most L for every L ≥ 1:
| Run length | Output length |
|---|
| 1 | 1 (a) |
| 2 | 2 (a2) |
| 9 | 2 (a9) |
| 10 | 3 (a10) |
| 100 | 4 (a100) |
So the compressed form is never longer than the input, and write never overtakes read. Compression that could expand the data would need a temporary buffer — and this encoding cannot expand it.
That argument is what an interviewer wants to hear before you write the code, because it justifies the whole approach.
The algorithm, and the trap inside it
Two pointers: one at the start of the current run, one scanning forward while the character stays the same. When it changes, emit char and count and move on. One pass, O(n).
The trap is what you emit into. result += ch + str(n) allocates a new string on every run, which makes the whole thing quadratic in the output length. Appending to a list and joining once is O(n). Interviewers ask this question partly to see which you reach for.
Return the shorter one
"abc" compresses to "a1b1c1", which is twice as long. The specification almost always says to return the original when compression does not help, and the check is one comparison at the end.
A common refinement is to bail out early once the output has already exceeded the input length, since it can never recover.
The in-place variant
The harder version gives you a character array and asks you to compress it in place, returning the new length. Because the compressed form is never longer than the original when it wins, a read-pointer/write-pointer pair works: read scans runs, write emits behind it, and write never overtakes read. That is the same two-pointer shape as the in-place dedupe.
Edge cases
| Input | Output | Length |
|---|
[] | [] | 0 |
["a"] | ["a"] | 1 |
["a","a"] | ["a","2"] | 2 |
["a","b","c"] | ["a","b","c"] | 3 — no counts added |
| Run of 10 | ["a","1","0"] | 3 |
| Run of 100 | ["a","1","0","0"] | 4 |
| All identical, 1000 chars | ["a","1","0","0","0"] | 5 |
Mixed case ["a","A"] | Two runs — case sensitive | 2 |
The run-of-10 and run-of-100 rows are the ones to test explicitly. An implementation that passes "aabbccc" and fails "a" * 12 is the common outcome.
The string version
If the input is a string rather than a character array, in-place is impossible — strings are immutable — so build a list and join:
Or with itertools.groupby, which is the idiomatic Python:
from itertools import groupby
def compress_groupby(s):
return "".join(
ch + (str(n) if (n := len(list(g))) > 1 else "")
for ch, g in groupby(s)
for n in [0] # awkward; see below
)
That last version is a good example of when not to be clever — the walrus placement fights the comprehension. The explicit loop is clearer:
groupby groups consecutive equal items, which is exactly what run-length encoding needs — and is why it works here without sorting, unlike its usual grouping use.
Run-length encoding in practice
This is run-length encoding, one of the oldest compression schemes, and it is still used where the data has long runs.
- Fax and bitonal images. Scanned documents are mostly white, giving very long runs. TIFF's Group 3 and 4 encodings are RLE-based.
- BMP and PCX image formats.
- Sparse matrices and bitmap indexes in databases, where long runs of zeros dominate.
- Inside other algorithms. The Burrows-Wheeler transform rearranges data to create runs, and then RLE compresses them — which is how bzip2 works.
Its weakness is equally clear: data without runs expands. Under a naive scheme that always writes a count, "abcdef" becomes "a1b1c1d1e1f1" — twice the size. This problem's rule of omitting counts of 1 is precisely the fix, and it is why the compressed output can never exceed the input.
Real formats handle it with escape codes distinguishing literal runs from repeated runs, which is what PackBits does.
What it is testing
Do you handle multi-digit counts? The primary trap, and it is what separates a working solution from one that passes the sample.
Do you omit counts of 1? The specification says so, and skipping it changes every answer.
Do you justify in-place safety? Explaining that output never exceeds input is the reasoning step.
Do you keep two independent pointers? Read and write advance at different rates, which is the pattern.
Do you know it is run-length encoding, and where it is used and why it can expand data?
Recap in one screen
- Count each run, write the character, and write the count only when it exceeds 1.
- Multi-digit counts must be written digit by digit — the main bug.
- In place is safe because 1 + digits(L) ≤ L for every run, so output never exceeds input.
- Read and write pointers advance independently; read always stays ahead.
- This is run-length encoding: excellent on data with long runs, and it expands data without them unless counts of 1 are omitted.