Count and Say
The count-and-say sequence is defined recursively: the first term is "1", and every later term is produced by reading the previous term aloud in digits — scanning it left to right and, for each run of identical adjacent digits, emitting the run's length followed by the digit itself. For example "1" reads as "one 1" → "11", which reads as "two 1s" → "21", which reads as "one 2, one 1" → "1211". Given an integer n, return the n-th term of the sequence as a string.
- 1 <= n <= 30
- Every term is a string of digits
n = 1"1"n = 4"1211"n = 5"111221"The count-and-say sequence is built by reading the previous term out loud, in digits. Start from term 1, the string "1". To make the next term, scan the current one left to right and, for each run of the same digit repeated, write down how many there were followed by which digit it was: "1" is a single 1, read as "one 1", written "11". Then "11" is two 1s, "21". Then "21" is one 2 then one 1, "1211". Given n, we return the n-th term as a string.
The definition is honestly the whole problem — there is no hidden trick waiting to be uncovered. The skill being tested is reading a precise, self-referential rule and turning it faithfully into code. Two consequences of that definition matter before we write anything. First, the sequence is strictly sequential: term n is defined only in terms of term n-1, so there is no shortcut that jumps straight to term n — we must generate every term from 1 up to n in order. Second, every term is itself a string of digits, and it is those digits, never their numeric value, that the next term describes.
Turning a term into the next one is a single, well-known operation called run-length encoding: replace each maximal run of identical symbols with the pair (count, symbol). To do it, walk the string with an index; at each new position start a run of length 1, then keep advancing while the next character equals the current one, tallying the length. When the run ends, emit the count as a digit followed by the digit itself, and continue from the character that broke the run.
result = "1" # term 1, the seed
for _ in range(n - 1): # read it (n - 1) times to reach term n
parts = []
i = 0
while i < len(result):
digit = result[i]
count = 1
while i + 1 < len(result) and result[i + 1] == digit:
count += 1
i += 1 # absorb the rest of this run
parts.append(str(count) + digit)
i += 1 # step to the next run
result = "".join(parts)
return resultjoin once at the end, rather than repeatedly doing result = result + piece inside the loop. In most languages a string is immutable, so + copies the entire accumulated string on every append — turning the construction of a length-L term into O(L²) work. Collecting pieces and joining once keeps each term's construction linear in its length. The same care applies to String Compression, which is run-length encoding under a different name.Each reading pass is linear in the length of the current term, and the term lengths grow — famously by a factor approaching Conway's constant, ≈ 1.303 per step — so the n-th term has length on the order of 1.303ⁿ and dominates the total work. The whole computation is therefore linear in the size of its own output, which itself grows exponentially in n; there is no way around producing that output, since the answer is the n-th term. (A curiosity that falls out of the rules, worth stating in an interview: starting from "1", no digit ever appears four times in a row, so a run count is never more than 3 — the sequence describes itself too tightly to permit it.) The transferable lesson is small but real: when a problem says "describe the previous thing" or "encode repeats compactly", the tool is run-length encoding, and its implementation trap is always the same — accumulate pieces in a list, join once.
count & say
Generating the 5th term from the 4th term: "1211".