On this page
Description
Describing a string by its runs, so "aaabcc" becomes "three a's, one b, two c's", is the heart of run-length compression, of the count-and-say sequence, and of every "longest streak" question. The scan is short: find where each run ends, then emit its length and value. The bugs are in the last run, in counts of 10 or more, and in data that has no runs worth compressing.
We'll go from simple to more technical:
- The pattern: an outer loop over runs and an inner loop that finds where each one ends.
- A second flavor: compression with counts that may have several digits.
- Where run-length encoding shows up in production (images, columnar storage, fax).
- What breaks it: the last run, multi-digit counts, data without runs.
The approach
Java
String nextTerm(String s) { // count and say: "1211" -> "111221"
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
int run = 0;
while (i < s.length() && s.charAt(i) == c) { run++; i++; } // consume the whole run
sb.append(run).append(c);
}
return sb.toString();
}
Python
def next_term(s: str) -> str: # count and say: "1211" -> "111221"
parts = []
i = 0
while i < len(s):
c = s[i]
run = 0
while i < len(s) and s[i] == c: # consume the whole run
run += 1
i += 1
parts.append(f"{run}{c}")
return "".join(parts)
# itertools.groupby finds the runs for you: "".join(f"{len(list(g))}{k}" for k, g in groupby(s))
The inner loop consumes an entire run, so the outer loop always starts exactly at the next run - and the last run is handled like every other one. The one-loop alternative ("if this character differs from the previous one, flush the run") has to remember to flush once more after the loop, and forgetting drops the last run.
Count-and-say starts from "1" and applies nextTerm repeatedly: 1, 11, 21, 1211, 111221, 312211, ... Only the digits 1, 2 and 3 ever appear and no run is longer than 3, so every count is a single digit. The length grows by about 30% per term (Conway's constant, about 1.3036): the 30th term already has 4,462 characters.
A second flavor: compression with multi-digit counts
Run-length encoding writes each character followed by its run length - here only when the run is longer than 1:
Java
String compress(String s) { // "aabcccccaaa" -> "a2bc5a3"
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
int run = 0;
while (i < s.length() && s.charAt(i) == c) { run++; i++; }
sb.append(c);
if (run > 1) sb.append(run); // append(int) writes every digit: 12 -> "12"
}
return sb.toString();
}
Python
def compress(s: str) -> str: # "aabcccccaaa" -> "a2bc5a3"
parts = []
i = 0
while i < len(s):
c = s[i]
run = 0
while i < len(s) and s[i] == c:
run += 1
i += 1
parts.append(c)
if run > 1:
parts.append(str(run)) # str() writes every digit: 12 -> "12"
return "".join(parts)
Runs can be longer than 9, so the count must be written as a number: sb.append((char) ('0' + run)) turns 10 into ':' and 12 into '<' (so does Python's chr(ord("0") + run) - write str(run)). And RLE only helps when runs are long - "abc" as "a1b1c1" doubles in size, which is why this version omits counts of 1. If the input itself can contain digits, "a12" becomes ambiguous (12 a's, or "a" then "1" twice?), so real formats restrict the alphabet or escape.
Where you'll see it
Fax machines encode each scan line as lengths of alternating white and black runs; BMP, TIFF (PackBits) and PCX images use RLE; columnar formats such as Parquet mix run-length and bit-packed encodings for repetitive columns; and compressed bitmaps (Roaring) store long stretches of set bits as runs.
Which tool for which job?
| You need | Use |
|---|---|
| Describe a string by its runs | an outer loop per run, with an inner loop to its end |
| Compress repeated characters | RLE with counts written as numbers |
| Never expand incompressible data | a packet scheme (PackBits: runs or literal blocks) |
| Columns in a database or file | sort first so equal values form runs, then RLE |
| General compression | DEFLATE or zstd, which handle runs and repeated substrings |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| No bounds check in the inner loop | reads past the end | i < n && s[i] == c |
| One-loop version without a final flush | the last run is dropped | emit it after the loop |
(char) ('0' + run) for the count | 10 becomes ':' | append(run) / str(run) |
| Char-plus-count RLE on random data | about double the size | PackBits-style literal blocks |
| Digits in the input | "a12" is ambiguous | restrict the alphabet, or escape |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why does the inner-loop scan need no special handling for the last run?
Show answer
The inner loop consumes each run completely and appends its description before the outer loop checks for more input. When the string ends, the last run has already been written. A one-loop version writes a run only when the next character differs, so it must flush once more after the loop.
2. What does sb.append((char) ('0' + run)) produce for a run of 12, and what's the fix?
Show answer
'<' - '0' + 12 is the character code 60, not the text "12". Use sb.append(run), which writes the number's digits.
3. When does run-length encoding make data bigger?
Show answer
When runs are short: every run costs a character plus a count, so "abc" becomes "a1b1c1". Omitting counts of 1 (or using literal packets) limits the damage.
Key takeaways
- Consume each run with an inner loop; the last run then needs no special case.
- Count-and-say only ever uses digits 1-3 and grows about 30% per term.
- Write counts with
append(int): runs can be 10 or longer. - RLE only pays off with long runs, and needs a digit-free alphabet or escaping to decode.