Problem Statement

Count and Say

This problem is built on a simple idea: read a string of digits out loud, the way a person would, and write down what you said. We call this run-length encoding, which just means "describe a string by counting how many times each digit repeats in a row." For example, if you read "1211" out loud you would say "one 1, one 2, two 1s," and writing those counts and digits gives you "111221." The count-and-say sequence starts at "1," and every next term is what you get by reading the previous term out loud. Your job is to find the nth term. The plan is to start at "1" and build each term from the one before it, scanning across groups of identical digits one group at a time.

mediumStringStringsTime: O(2^n) · Space: O(2^n)

Signals to notice

describe previous term's digit groupsrun-length encodingiterative build

Brute force first

Not applicable — iterative IS the only approach.

The key insight

Start from '1'. Each step: scan for consecutive same digits, output count + digit. O(n × length).

Trace it on `n=4`

init: result="1" (countAndSay(1)), loop runs n-1=3 times
iter1: scan "1" -> group (count=1,'1') -> append "11"; result="11"
iter2: scan "11" -> group (count=2,'1') -> append "21"; result="21"
iter3: scan "21" -> group (1,'2') append "12", then group (1,'1') append "11" -> result="1211"
loop ends after 3 iters -> return "1211"

What must stay true

Each term is the run-length encoding of the previous term. The transformation is deterministic.

Shape of the loop

result = "1"
repeat (n-1) times:
    i = 0; next = ""
    while i < len(result):
        count = run length of result[i] starting at i
        next += str(count) + result[i]; i += count
    result = next
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting the last digit group — output it after the loop ends.

Strings Pattern