LeetCode #38 — Medium

Count and Say

A complete visual walkthrough of the look-and-say sequence — building each term by describing the previous one.

The Problem

Problem Statement

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"
countAndSay(n) is the run-length encoding of countAndSay(n - 1).

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511".

Given a positive integer n, return the n^th element of the count-and-say sequence.

Example 1:

Input: n = 4

Output: "1211"

Explanation:

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

Example 2:

Input: n = 1

Output: "1"

Explanation:

This is the base case.

Constraints:

1 <= n <= 30

Follow up: Could you solve it iteratively?

Roadmap

Understanding the Pattern
The Core Insight — Group and Count
Walkthrough — Generating Terms 1 through 5
Edge Cases
Full Annotated Code
Interactive Demo
Complexity Analysis

Step 01

Understanding the Pattern

The count-and-say sequence starts with "1". Each subsequent term is created by reading aloud the previous term — describing what you see:

The Sequence

n=1

← base case

n=2

← "one 1"

n=3

← "two 1s"

n=4

← "one 2, one 1"

n=5

← "one 1, one 2, two 1s"

💡

Read it out loud! Term 4 is "1211". Reading it: "one 2, one 1" — which becomes "1211". Wait, that's the same! No: reading "1211" gives "one 1, one 2, two 1s" = "111221". Each term describes the previous, not itself.

Step 02

The Core Insight — Group and Count

To build term n from term n-1, we scan left-to-right and group consecutive identical digits. For each group, we output [count][digit].

From "1211" to "111221"

Previous term: "1211" — let's group it:

1 x "1"

1 x "2"

2 x "1"

↓ encode as [count][digit] ↓

Result: "111221"

⚡

The algorithm is iterative: Start with "1", repeat n-1 times: scan the current string, count consecutive duplicates, build the next string. No recursion needed — just a loop within a loop.

Step 03

Walkthrough — Generating Terms 1 through 5

Let's trace the algorithm step by step, showing how each term generates the next:

Term 1 → Term 2

Current: "1"

Scan: one group of "1" (count=1). Output: "1" + "1" = "11"

Term 2 → Term 3

Current: "11"

Scan: one group of "1,1" (count=2). Output: "2" + "1" = "21"

Term 3 → Term 4

Current: "21"

Scan: group "2" (count=1), group "1" (count=1). Output: "1""2" + "1""1" = "1211"

Term 4 → Term 5

Current: "1211"

Scan: group "1" (count=1), group "2" (count=1), group "1,1" (count=2). Output: "1""1" + "1""2" + "2""1" = "111221"

Step 04

Edge Cases

n = 1 Base case — return "1" immediately, skip the loop entirely.
Large n The string grows exponentially. n=30 produces a string with 5,808 characters. The constraint is n <= 30.
No digit > 3 A fascinating property: for the standard sequence starting from "1", no digit ever exceeds 3. A run of 3 identical digits always breaks in the next term.
Last group Don't forget to append the final group after the loop ends — it's a common bug to miss it.

Step 05

Full Annotated Code

class Solution {
    public String countAndSay(int n) {

        String result = "1";                // base case: term 1

        for (int i = 1; i < n; i++) {        // build terms 2..n
            StringBuilder sb = new StringBuilder();
            int count = 1;                    // count of current digit

            for (int j = 1; j < result.length(); j++) {
                if (result.charAt(j) == result.charAt(j - 1)) {
                    count++;                  // same digit — extend group
                } else {
                    sb.append(count)           // different digit — emit group
                      .append(result.charAt(j - 1));
                    count = 1;                // start new group
                }
            }
            // Don't forget the last group!
            sb.append(count)
              .append(result.charAt(result.length() - 1));

            result = sb.toString();
        }
        return result;
    }
}

func countAndSay(n int) string {

    result := "1"                        // base case: term 1

    for i := 1; i < n; i++ {             // build terms 2..n
        var sb []byte
        count := 1                       // count of current digit

        for j := 1; j < len(result); j++ {
            if result[j] == result[j-1] {
                count++                  // same digit — extend group
            } else {
                // different digit — emit group
                sb = append(sb, byte('0'+count), result[j-1])
                count = 1               // start new group
            }
        }
        // Don't forget the last group!
        sb = append(sb, byte('0'+count), result[len(result)-1])

        result = string(sb)
    }
    return result
}

class Solution:
    def count_and_say(self, n: int) -> str:

        result = "1"                      # base case: term 1

        for _ in range(1, n):             # build terms 2..n
            sb: list[str] = []
            count = 1                     # count of current digit

            for j in range(1, len(result)):
                if result[j] == result[j - 1]:
                    count += 1            # same digit — extend group
                else:
                    sb.append(str(count) + result[j - 1])
                    count = 1             # start new group

            # Don't forget the last group!
            sb.append(str(count) + result[-1])

            result = "".join(sb)
        return result

impl Solution {
    pub fn count_and_say(n: i32) -> String {

        let mut result = String::from("1");   // base case: term 1

        for _ in 1..n {                        // build terms 2..n
            let chars: Vec<char> = result.chars().collect();
            let mut sb = String::new();
            let mut count = 1usize;           // count of current digit

            for j in 1..chars.len() {
                if chars[j] == chars[j - 1] {
                    count += 1;              // same digit — extend group
                } else {
                    // different digit — emit group
                    sb.push_str(&count.to_string());
                    sb.push(chars[j - 1]);
                    count = 1;              // start new group
                }
            }
            // Don't forget the last group!
            sb.push_str(&count.to_string());
            sb.push(*chars.last().unwrap());

            result = sb;
        }
        result
    }
}

function countAndSay(n: number): string {

    let result = "1";                    // base case: term 1

    for (let i = 1; i < n; i++) {        // build terms 2..n
        let sb = "";
        let count = 1;                    // count of current digit

        for (let j = 1; j < result.length; j++) {
            if (result[j] === result[j - 1]) {
                count++;                  // same digit — extend group
            } else {
                sb += count + result[j - 1]; // different digit — emit group
                count = 1;                // start new group
            }
        }
        // Don't forget the last group!
        sb += count + result[result.length - 1];

        result = sb;
    }
    return result;
}

⚡

Common pitfall: The inner loop starts at j=1 and compares with j-1. After the loop exits, the last group hasn't been appended yet. The final sb.append(count).append(lastChar) handles this. Forgetting it is the most frequent bug.

Step 06

Interactive Demo

Enter a value for n, then step through the generation process. Watch how each term is built from the previous by grouping consecutive digits.

Sequence Generator

n (1-15)

Step 07

Complexity Analysis

Time

O(2ⁿ)

Space

O(2ⁿ)

Each term is generated from the previous by a single linear scan. However, the string length grows roughly exponentially -- each term can be up to 2x the length of the previous. The total work to generate the n^th term sums across all iterations to O(2ⁿ). Space is dominated by the largest string stored (the final term).

Approach Breakdown

BRUTE FORCE

O(2n) time

O(2n) space

There is no shortcut to skip terms -- each must be built from the previous. The outer loop runs n-1 times and the inner loop scans the current string, which roughly doubles in length each iteration. Total work sums to O(2ⁿ).

OPTIMAL

O(2n) time

O(2n) space

Iterative generation with a single linear scan per term using a StringBuilder. Each term is processed in one pass by counting consecutive identical digits. Space is dominated by the final string, which grows as Lⁿ where L ~ 1.30 (Conway's constant).

🎯

This is the Morris number sequence. The sequence length grows roughly as Lⁿ where L ~ 1.303577 (Conway's constant). Each term is at most 2x the previous. Since n is capped at 30, the final string has at most ~5,800 characters -- well within practical limits.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.