Run-length string compression

Walk the string counting runs of equal characters and append each char + count to a list, joined at the end. Building with += makes it O(n²) — which is half of why this question is asked. Return the original unless the compressed form is genuinely shorter.

StringsCoding problemMedium

Step through it

What to watch

  • Each highlighted block is one run, consumed in a single step.
  • The output grows by two characters per run, not per input character.
  • The final check is the part most people forget.

Say this out loud

"Count runs, append to a list, join at the end - never += in the loop. And return the original if compression didn't help, which 'abc' doesn't."

Overview

Run-length encoding stores each repeated character with its count. For the interview variant, write runs into a mutable array and return the compressed prefix only when it is shorter than the original.

In this guide
  1. Run it: Run-length string compression in code
  2. The solution
  3. Why in-place is safe
  4. The algorithm, and the trap inside it
  5. Return the shorter one
  6. The in-place variant
  7. Edge cases
  8. The string version
  9. Run-length encoding in practice
  10. Sources and next steps

Run it: Run-length string compression in code

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.

1Python
Output
2Python
Output
3Python
Output

The solution

4Python
Output

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 lengthOutput length
11 (a)
22 (a2)
92 (a9)
103 (a10)
1004 (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

InputOutputLength
[][]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 sensitive2

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:

5Python
Output

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:

6Python
Output

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.

Sources and next steps

How the code works

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.

How the code works

  1. parts.append(...)The list is the whole point. out += ... allocates a new string per run, so the output building is quadratic even though the scan is linear.
  2. while j < len(text) and text[j] == text[i]:The inner loop consumes an entire run in one go, so the outer loop runs once per run rather than once per character. Both pointers only move forwards.
  3. return out if len(out) < len(text) else textThe rule people forget. "abc" compresses to something twice as long, and the specification almost always asks for the shorter of the two.
  4. write never overtakes readWhy the in-place version is safe: whenever compression wins, the written prefix is shorter than the part already consumed, so it cannot clobber unread input.

Change one thing

  • Compress a string of 10,000 distinct characters. The output is twice the input and the original comes back — check the early exit would have saved the work.
  • Add the early bail-out: stop as soon as the output length reaches the input length, since it can never recover.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. Why append to a list rather than build the result with +=?

  2. compress('abc') should return:

  3. The in-place variant is safe because:

Cheat sheet

Run-length string compression

Compress aabcccccaaa into a2b1c5a3 with a single scan. Count consecutive runs, build the result, and return the original when compression is longer.

INTERVIEW · vizlearn.in/interview/string-compression.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.