Count and Say: Run-Length Encoding as a Simulation
How to generate the nth term of the Count and Say sequence with a single-pass run-length scan — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Count and Say looks like a riddle before it looks like an algorithm. You start with "1", and each new term is produced by reading the previous term out loud: "1" is "one 1", which you write as "11"; "11" is "two 1s", which you write as "21"; and so on. Your job is to return the nth term of that chain.
There is no clever data structure to reach for and no math shortcut to derive. The entire problem is a simulation — you have to build each term literally, one group of digits at a time. What makes it a real interview problem is the inner loop: reading a term correctly means grouping consecutive identical digits with a run-length scan, and getting the trailing group right is where most people slip.
Once you see the run-length pattern underneath, the code writes itself.
The problem
The Count and Say sequence is defined recursively. Term 1 is "1". To get term k, you read term k-1 aloud: scan it left to right, and for every run of the same digit, emit the length of the run followed by the digit itself. Given an integer n, return term n as a string.
Input: n = 4
Output: "1211"
Term 1: "1" (the seed)
Term 2: "11" one 1 -> "1" + "1"
Term 3: "21" two 1s -> "2" + "1"
Term 4: "1211" one 2, one 1 -> "1" + "2", "1" + "1"Two facts about the sequence keep it tractable: every term contains only the digits 1, 2, and 3 (a run of four identical digits can never form), and each term is built purely from the string of the previous term — you never need any earlier term. That means a single string variable, rewritten n-1 times, is all the state you need.
The brute force baseline
The shortcut everyone reaches for first is a regular expression. JavaScript can match every run of identical characters with /(.)\1*/g, then map each match to its length plus its first character:
function countAndSay(n) {
let s = '1';
for (let iter = 1; iter < n; iter++) {
s = s.replace(/(.)\1*/g, (run) => run.length + run[0]);
}
return s;
}This is correct and short. The problem is that it hides the mechanics behind the regex engine — in an interview you can't explain how the grouping happens, and "I'd use a regex" is rarely the answer the interviewer is fishing for. Regex-driven backtracking also gives you no control over the scan, and the moment the follow-up becomes "do it without regex" (a common one), you're back to writing the loop by hand anyway.
The complexity, notably, is the same as the hand-written version — regex or not, you still touch every character of every intermediate string. So the switch to the explicit scan costs nothing and buys you a solution you can actually narrate.
The key insight: run-length encoding, one pass per term
"Say what you see" is exactly run-length encoding. To read a term, you walk it once while tracking two things: the digit you're currently inside a run of (char) and how many of them you've seen in a row (count). Every time the next digit matches, you extend the run. Every time it differs, you flush the run you just finished — append count then char to the next term — and start a fresh run at the new digit.
The one detail that separates a working solution from an off-by-one bug: the loop ends while you're still inside the final run. That last group has been counted but never flushed, so you must append it explicitly after the loop. Forget it and every term loses its tail.
Outside that inner scan sits a simple driver: start at "1" and repeat the read n-1 times. Term by term, the string grows — roughly 30% longer each step — but the logic never changes.
The optimal solution
This mirrors the algorithm the visualizer steps through, variable names and all:
var countAndSay = function(n) {
let s = '1';
let iter = 1;
while (iter < n) {
let nextS = '';
let count = 1;
let char = s[0];
for (let i = 1; i < s.length; i++) {
if (s[i] === char) {
count++;
} else {
nextS += count + char;
char = s[i];
count = 1;
}
}
nextS += count + char;
s = nextS;
iter++;
}
return s;
};Trace the responsibilities: s is always the current term, nextS accumulates the term being built, and count/char describe the run in progress. The for loop starts at index 1 because char is seeded from index 0 — you never compare a digit to itself. The single most important line is nextS += count + char after the loop: it flushes the trailing run that the loop body never reaches.
Note that count + char relies on JavaScript coercing the number count and the string char into a concatenation — 2 + '1' becomes "21", not 3. That implicit string build is exactly the "count, then say" step.
Walkthrough
Here is countAndSay(4) in full. The outer rows show each term being produced; the indented scan of term 3 ("21" becoming "1211") exercises both the match and the mismatch branch.
| iter | s (reading) | i | s[i] | char | count | nextS | Action |
|---|---|---|---|---|---|---|---|
| 1 | "1" | — | — | '1' | 1 | "" | loop skipped (length 1); flush → nextS = "11" |
| 2 | "11" | 1 | '1' | '1' | 2 | "" | s[1] matches char → count = 2; flush → "21" |
| 3 | "21" | 1 | '1' | '2' | 1 | "" | s[1] ≠ char '2' → flush "12", reset char='1', count=1 |
| 3 | "21" | — | — | '1' | 1 | "12" | loop ends; flush final run → nextS = "1211" |
| 4 | "1211" | iter = 4, not < n → return "1211" |
The row that teaches the trap is the second row for iter = 3. The scan loop finished after processing index 1, but the run of a single '1' was still open. Only the post-loop flush turns "12" into "1211". Drop that line and you'd return "12" — a silent, plausible-looking wrong answer.
Complexity
Let L be the length of the final term (term n).
| Approach | Time | Space | Why |
|---|---|---|---|
| Regex simulation | O(n · L) | O(L) | one pass over each of the n-1 intermediate strings |
| Run-length scan | O(n · L) | O(L) | each term is read once; work is linear in its length |
Both approaches are O(n · L) time because you build n-1 terms and each read is linear in the string's length, and the later terms dominate. Space is O(L) — you only ever hold the current term and the one being built. The subtlety is that L itself grows exponentially in n (by a constant factor near 1.303, Conway's constant), so the string length, not n, is the real cost driver for large inputs.
Common mistakes
- Forgetting the final flush. The loop exits mid-run. Without the
nextS += count + charafter the loop, every term drops its last group. - Starting the scan at index 0. If you seed
char = s[0]you must start the loop ati = 1. Starting at0comparess[0]to itself and double-counts the first digit. - Doing math instead of concatenation.
count + charmust produce a string. Ifcharis ever a number,2 + 1gives3instead of"21". Keep the term as a string throughout. - Recomputing from term 1 every time. Each term depends only on its immediate predecessor. Rebuilding the whole chain inside the loop turns an O(n·L) solution into something far slower.
- Assuming digits above 3 appear. They never do, but relying on that is fine only for validation — the grouping logic must stay general.
Where this pattern shows up next
Count and Say is your gateway into string-simulation problems — the ones where the whole task is to faithfully transform a string character by character:
- Decode String — the inverse idea: expand a run-length-style encoding like
3[a]2[bc]back into its full form using a stack. - Reverse Words in a String — another single-pass scan where grouping (into words) and careful edge handling decide correctness.
- Minimum Add to Make Parentheses Valid — a running-counter scan, the same "track state as you walk" discipline applied to brackets.
- Sum of Beauty of All Substrings — frequency counting across substrings, extending the count-as-you-go habit.
You can also step through Count and Say interactively to watch each run flush into the next term and see the string length climb term by term.
FAQ
Why is Count and Say considered a simulation problem?
Because there is no formula that jumps directly to the nth term. The definition is recursive and self-referential — term k is literally the spoken reading of term k-1 — so the only way to get the answer is to build every term in order and read it aloud in code. The "algorithm" is just faithfully modelling that reading process with a run-length scan. That is the definition of a simulation: you reproduce the described procedure step by step rather than deriving a shortcut.
What is the time complexity of Count and Say?
It is O(n · L), where L is the length of the final term. You generate n-1 terms, and reading each one costs time linear in its length, with the later (longer) terms dominating the total. Space is O(L) because you only keep the current term and the one being built. The catch is that L grows exponentially in n — by a factor of about 1.303 per term (Conway's constant) — so the real cost is driven by string length, not by n directly.
How do I avoid the off-by-one bug in Count and Say?
The bug comes from the scan loop ending while you are still inside the last run of digits. During the loop you only flush a group when the digit changes; the final group never triggers a change, so it is left unwritten. Fix it by appending count + char one more time immediately after the loop finishes. Pair that with seeding char = s[0] and starting the loop at index 1, and both ends of the scan are handled correctly.
Why do only the digits 1, 2, and 3 appear in the sequence?
A digit's count in the output equals the length of a run in the input. It turns out no run in any Count and Say term is ever longer than three, so no count above 3 is ever emitted. Intuitively, a run of four identical digits like "1111" would require the previous term to have produced four 1s in a row, and the reading rules never generate that configuration. You do not need to prove this to solve the problem — the scan works for any run length — but it is a useful sanity check that your output is well-formed.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.