cf.completefrontend
STRING ALGORITHMS · FOUNDATION

Run-length encoding

Shrink repeated characters by writing each run once with its count, like aaabcc becoming a3b1c2.

Time O(n)Space O(n)5 practice problemsStep-through picture

The idea

A run is a group of the same character in a row. aaabcc has three runs: aaa, b, and cc. Run-length encoding writes each run as the character and how many times it repeats: a3b1c2.

To do it, walk the text and remember where the current run started, in runStart. When the character changes, or the text ends, the run is over. Its length is i - runStart. Write it out and start a new run at i.

This is one of the oldest compression ideas. It works well when data has long runs, like a row of pixels that are all white, and badly when nothing repeats, since abc becomes the longer a1b1c1.

An everyday example

Reading out a row of colored beads

You describe a bead necklace over the phone. Instead of saying "red, red, red, red, blue, blue", you say "four red, two blue". You keep your finger on the first bead of the current color group and slide another finger forward. When the color changes, you count the beads between your fingers, say the number and the color, and move the first finger to the new color.

How the example maps to the code
In the exampleIn the code
The first bead of the current color grouprunStart
The finger that slides forwardi
The color changes, or the necklace endsi === text.length || text[i] !== text[runStart]
Saying "four red"parts.push(text[runStart] + (i - runStart))

From the slow way to run-length encoding

  1. Start with the cost of storing everything as it is. A row of 1,000 pixels where 990 are white takes 1,000 values, even though it says very little. A smarter format writes each repeated value once, with a count of how many times it repeats.
  2. To write that, you need to know where each run starts and ends. A run ends exactly where the character changes, so you only need to compare each character with the first character of the current run. Keep the index of that first character in runStart.
  3. When text[i] differs from text[runStart], the run covers indexes runStart to i - 1, so its length is i - runStart. Write the character and that length, and start the next run at i. Each character is looked at once.
  4. The last run never meets a different character; it meets the end of the text. Letting i go one step past the last index, to text.length, and treating that as a change writes the last run with the same code. Walk, compare with the run's first character, write when it changes: that loop is run-length encoding.

How it works

  1. Make an empty array parts for the output, and set runStart = 0.
  2. Move i from 1 up to and including text.length.
  3. If i reached the end, or text[i] differs from text[runStart], the run from runStart to i - 1 is finished.
  4. Push the run's character and its length i - runStart into parts, then start the next run with runStart = i.
  5. Return parts.join("").

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function runLengthEncode(text) {
  2. const parts = [];
  3. let runStart = 0;
  4. for (let i = 1; i <= text.length; i++) {
  5. if (i === text.length || text[i] !== text[runStart]) {
  6. parts.push(text[runStart] + (i - runStart));
  7. runStart = i;
  8. }
  9. }
  10. return parts.join("");
  11. }

How fast it is

TimeO(n)
Extra memoryO(n)

One pass over the text with constant work per character. The output has one piece per run.

  • Best caseO(n)

    Any text: every character is compared once. One long run, like wwwwwwwwwwww, pushes just one piece, w12.

  • Average caseO(n)

    Ordinary text: one comparison per character and one push per run.

  • Worst caseO(n)

    No repeats, like abcdef: one push per character, and the output, a1b1c1d1e1f1, is twice as long as the input.

Common mistakes

  • Forgetting to write the last run. If the loop stops at i < text.length, the final run is never pushed.
  • Reading a count like 12 as two counts when decoding. Collect all consecutive digits into one number.
  • Assuming encoding always makes text shorter. With few repeats, abc becomes a1b1c1. Compare lengths if the task says to keep the shorter one.
  • Encoding text that contains digits with a format that writes the count after the character. a11 could mean a eleven times or a once then 1 once. Pick a format that can't be confused, or escape digits.

When to use it

Look for these clues in a problem:

  • The input has long stretches of the same value, like pixels, seats, or status codes.
  • The task mentions compressing, collapsing repeats, or counting consecutive equal items.
  • You need to expand a compact form like 3a2b back into full text.
  • Two encoded lists must be combined without expanding them first.

Check yourself

Answer each one in your head first, then open it.

Why does the loop run up to i <= text.length and not i < text.length?

So the last run is written by the same if. At i === text.length the run must end, and the || stops before reading past the text.

What does runLengthEncode("aabbbaa") return?

a2b3a2. The two runs of a stay separate, because they aren't next to each other.

How many pieces does parts hold for n characters where no two neighbors are equal?

n: every character is its own run, so the output is twice as long as the input.

Why compare with text[runStart] and not text[i - 1]?

Both work, because every character in the current run equals its first one. text[runStart] makes the question clear: is this still the same run?

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of each loop: parts holds the encoding of text.slice(0, runStart), and every character from runStart to i - 1 equals text[runStart]. At i = 1, parts is empty, runStart is 0, and the piece from 0 to 0 is a single character, so the rule holds.

Each step keeps it. If text[i] equals text[runStart], the current run just gets one longer. If it differs, or i is the end, the run from runStart to i - 1 is complete and can't grow, so pushing text[runStart] + (i - runStart) makes parts encode text.slice(0, i). Moving runStart to i starts the next run.

The loop ends after i = text.length, which always counts as a change. At that point runStart equals text.length, so parts encodes the whole text, one piece per run, and join("") glues the pieces together.

Going deeper

3 more ideas

Why the loop goes one step past the end

A run is only written when it ends, and the last run ends at the end of the text, not at a different character. Letting i reach text.length and treating that as "the run ended" writes the last run without a separate step after the loop.

How fast it is

Each character is looked at once, so it is O(n) time. The output holds one piece per run, at most n pieces, so the extra memory is O(n) in the worst case and much less when runs are long.

Decoding, and counts with more than one digit

To decode a12b3, read a character, then read all the digits after it as one number: 12, not 1 and then 2. Then repeat the character that many times with char.repeat(count). Many formats put the count first instead, like 12a3b; read the digits first in that case.

Work it by hand

Every step in a table, with why

Encode 8 characters with a run of 3, a run of 1, and a run of 4 that only ends at the end of the text.

text = "hhhjkkkk"

Stepitext[i]Run ends?runStartpartsWhat happensWhy
11hno0[]same as text[0]The run of h grows to 2.
22hno0[]same as text[0]The run of h grows to 3.
33jyes3["h3"]push h and 3 - 0j differs from h, so the run from 0 to 2 ends, with length 3 - 0 = 3. The next run starts at 3.
44kyes4["h3", "j1"]push j1A run of one character still gets a count, 1.
55kno4["h3", "j1"]same as text[4]The run of k grows.
66kno4["h3", "j1"]same as text[4]Still k.
77kno4["h3", "j1"]same as text[4]The last character of the text. The run isn't written yet.
88-yes (end)8["h3", "j1", "k4"]push k4i === text.length, so the last run ends with length 8 - 4 = 4. The || stops before reading text[8].

It returns h3j1k4: 6 characters instead of 8. The loop ran 8 times, once for each i from 1 to text.length.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Run-length encodingO(n)O(n)The data has long runs of one value: blank pixels, padding, or repeated lines.
Counting with a MapO(n)O(n)You need how many times each character appears in total, not in a row. The order is lost.
Huffman codingO(n log n)O(n)Values repeat often but not next to each other; common values get shorter codes.
A general compressor like gzipO(n)O(n)Real files and network traffic: it finds repeated pieces anywhere, not only runs, and browsers support it already.

Extra memory: O(r) for parts with r runs: O(n) when nothing repeats, and tiny when runs are long.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Run-length encoding and the other approaches, on a scale where each line up is 10 times more steps.
  • Run-length encoding, Counting with a Map, A general compressor like gzip O(n)
  • Huffman coding O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Run-length encoding101,0001 million
Counting with a Map101,0001 million
Huffman coding339,96620 million
A general compressor like gzip101,0001 million

Inputs that need care

5 tricky inputs
Empty text: ""
The loop starts at i = 1, which is already past text.length, so it never runs and returns "".
One character: "q"
At i = 1, i === text.length, so it pushes q1 and returns q1.
A run of 12: "wwwwwwwwwwww"
It returns w12. A decoder must read 12 as one number, not as 1 and then 2.
Digits in the text: "1112"
It returns 1321, which could also be read as 1 repeated 321 times. Use a format that can't be confused, like counts in brackets, or escape the digits.
Emoji: "😀😀"
Each emoji is two code units, and text[i] reads one unit at a time, so the halves alternate and form four runs of 1. The output splits the emoji apart. Walk Array.from(text) instead to handle whole characters.

Variations and follow-ups

Twists interviewers add

Keep the shorter one

Encoding can make text longer. A common rule returns the encoded text only when it's shorter than the original, so abc stays abc, while aaaab becomes a4b1.

Skip counts of 1

Write a run of length 1 as just the character: hhhjkkkk becomes h3jk4. It's shorter, but the decoder must check whether digits follow each character.

Runs of pixels

Fax images and some early bitmap formats store each row of pixels as alternating run lengths of white and black. They don't write the colors at all, since the colors take turns.

Grouping neighbors in any list

The same loop groups any list by equal neighbors, like log lines from the same user in a row, or chat messages from one sender. Instead of a count, push the slice from runStart to i.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "compress", "consecutive", "in a row", or "group repeated characters". "Consecutive" is the key word: total counts would call for a hash map instead.
  • Name the two moments when a run ends, the character changes or the text ends, and show how the loop up to i <= text.length handles both with one if.
  • Test by hand: an empty string, one character, and a run longer than 9. The last one checks that counts with two digits are written and read correctly.
  • The usual follow-up is decoding, or encoding in place in an array of characters. For in place, keep a write index behind the read index; skipping counts of 1 guarantees the output never gets longer than the input.

Where frontend code uses it

The same idea in real UI code
  • Image formats compress runs of equal pixels; for example, PNG's compression and the old BMP RLE modes both benefit from long runs of the same color.
  • Analytics dashboards collapse repeated events into "Click x 5" rows, which is run-length encoding of the event stream.
  • Chat apps group consecutive messages from the same sender under one name and avatar; that grouping is finding runs in the message list.

Related algorithms