vizlearn

Run-length string compression

Interview QuestionsBy Updated

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.

Overview

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.

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."

Run-length string compression

Compress 'aabcccccaaa' to 'a2b1c5a3'. Return the original if the compressed form is not shorter.

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.

Run it in Python

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.

compression.pyPython 3
Output
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
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.
INTERVIEW · vizlearn.in/interview/string-compression.html
More in Interview
InterviewLongest common prefixInterviewImplement substring search (strStr)InterviewIsomorphic stringsInterviewWhat is a Python list underneath?
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.
About VizLearnGitHubLinkedInContact