Count and Say: Brute Force to Optimal

LeetCode 38, solved three ways — recursive, iterative, and an optimized iterative version — with intuition, C++ code, an animated dry run for each approach, and complexity analysis you can explain out loud.

⏱ 8 min read🧩 Strings · Recursion · Simulation🎯 Difficulty: MediumOn this page

1. Problem statement
2. Approach 1 — Brute force (recursive)
3. Approach 2 — Better (iterative bottom-up)
4. Approach 3 — Optimal (iterative + efficient buffer)
5. Complexity comparison
6. Interview notes
7. FAQ

Problem Statement

Given a positive integer n, return the nth term of the count-and-say sequence.

countAndSay(1) = "1", and every later term is the run-length encoding of the previous term — replace each maximal run of identical digits with "count followed by digit".

Example: for n = 4:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

To keep every approach grounded in the same example, we'll trace how each one produces "1211" from "21" — once through a recursive call stack, once through a plain iterative scan, and once through an optimized single-pass buffer.

Approach 1 · Brute Force

Recursive Definition, Applied Literally

Intuition

The problem statement itself is a recurrence: countAndSay(n) depends on countAndSay(n-1). The most literal way to solve it is to translate that definition directly into a recursive function — call for the previous term, then run-length-encode whatever comes back.

It's the first working solution most people write, but two things make it the "brute" version here: it pays for a recursive call stack it doesn't need, and if you build the encoded result with plain string concatenation (result = result + ...), each concatenation silently creates a brand-new string object instead of extending one in place.

Algorithm

1. Base case: if n == 1, return "1".
2. Otherwise, recursively call countAndSay(n - 1) to get the previous term.
3. Scan the previous term left to right, grouping consecutive identical digits.
4. For each group, append count followed by the digit to the result by reassigning a new string (result = result + ...).
5. Return the assembled result.

C++ Code

string countAndSay(int n) {
    if (n == 1) return "1";

    string prev = countAndSay(n - 1);   // recursive call
    string result = "";
    int i = 0;

    while (i < (int)prev.size()) {
        char ch = prev[i];
        int count = 0;
        while (i < (int)prev.size() && prev[i] == ch) {
            count++;
            i++;
        }
        // naive concatenation: builds a brand-new string every time
        result = result + to_string(count) + string(1, ch);
    }
    return result;
}

Dry Run

Complexity Analysis

Approach 2 · Better

Build It Bottom-Up, Iteratively

Intuition

Since countAndSay(n) only ever needs the term right before it, there's no reason to recurse at all. Start from "1" and walk forward, run-length-encoding each term to produce the next one, stopping once you reach term n. This directly answers the problem's own follow-up: "could you solve it iteratively?"

Algorithm

1. Start with current = "1".
2. Loop level from 2 to n.
3. Scan current left to right with two pointers, grouping consecutive identical digits and their counts.
4. Append count then the digit to a fresh string next using += (in-place append, not full reconstruction).
5. Set current = next and continue; after the loop, current is the answer.

C++ Code

string countAndSay(int n) {
    string current = "1";

    for (int level = 2; level <= n; level++) {
        string next = "";
        int i = 0;
        while (i < (int)current.size()) {
            char ch = current[i];
            int count = 0;
            while (i < (int)current.size() && current[i] == ch) {
                count++;
                i++;
            }
            next += to_string(count);   // in-place append
            next += ch;
        }
        current = next;
    }
    return current;
}

Dry Run

Complexity Analysis

Approach 3 · Optimal

Iterative + a Single Efficient Buffer

Intuition

The iterative version is already solid, but two small inefficiencies remain: to_string(count) allocates a temporary string just to hold one digit, and rebuilding next from an empty string on every level can force multiple reallocations as it grows. Both are fixable with a fact specific to this sequence: a run of the same digit never has length greater than 3 (a known property of the look-and-say sequence), so the count is always a single digit — you can append it as a character directly, no to_string needed.

Algorithm

1. Start with current = "1".
2. reserve() capacity for next up front to avoid repeated buffer growth.
3. Scan current with two pointers exactly as before, but append the run count as '0' + count (a single character) instead of calling to_string.
4. Move next into current with std::move to avoid an extra copy.
5. Repeat until level n, then return current.

C++ Code

string countAndSay(int n) {
    string current = "1";

    for (int level = 2; level <= n; level++) {
        string next;
        next.reserve(current.size() * 2); // avoid repeated reallocation
        int i = 0;
        int sz = (int)current.size();

        while (i < sz) {
            char ch = current[i];
            int count = 0;
            while (i < sz && current[i] == ch) {
                count++;
                i++;
            }
            next += char('0' + count); // runs never exceed 3, so this is safe
            next += ch;
        }
        current = move(next);
    }
    return current;
}

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

• Write the recursive version first if it comes naturally — it mirrors the problem statement exactly — but immediately flag that it's not needed since each term only depends on the one directly before it.
• Pivot to the iterative version proactively; the problem's own follow-up asks for it, so bringing it up before being asked shows you read the prompt closely.
• If asked to optimize further, mention the "no run longer than 3" property of the look-and-say sequence — it's a nice piece of problem-specific insight that most candidates miss, and it justifies skipping to_string().

Common follow-ups

• "Could you solve it iteratively?" → this is the official follow-up; walk through the bottom-up version directly.
• "What if n were very large, like 10⁵?" → discuss that the string length grows by roughly Conway's constant (~1.303x) per term, so even moderate n produces enormous strings — worth mentioning as a real scaling limit.
• "Can you avoid storing every previous term?" → you only ever need the immediately previous term, so a single rolling current string (as shown above) is already optimal on memory.

Edge cases to mention

• n = 1 → return "1" directly, no scanning needed.
• A single run spanning the entire string (e.g. "111") → the two-pointer scan should still terminate cleanly at the string's end.
• Off-by-one errors in the inner while-loop bound (i < size) are the most common bug — test with a term that ends mid-run.

Related problems

• String Compression (LeetCode 443)
• Run-Length Encoding / Decoding
• Look-and-Say sequence variants
• Two-pointer grouping problems in general

Frequently Asked Questions

What is the Count and Say sequence?

It's a sequence where each term describes the previous term using run-length encoding, starting from the base term "1". Reading a term out loud — "one 1", "two 1s", "one 2 one 1" — literally produces the next term.

Which approach should I lead with in an interview?

Write the iterative bottom-up version as your primary solution since it directly answers the stated follow-up question, then mention the recursive version only to show you understand the recurrence, and bring up the buffer/allocation optimizations if asked to go further.

What is the time complexity of Count and Say?

Producing all n terms takes time proportional to n times the length of the longest term, since each term requires exactly one linear scan of the term before it.

Can a digit repeat more than 3 times in a row?

No — this is a known property of the look-and-say sequence. Because of it, a run's count is always a single digit, which is what makes it safe to append the count as one character instead of using a general integer-to-string conversion.

video link:

code link