Count and Say
Count and Say: term 1 is \"1\"; each next term reads the previous aloud (\"1211\" → one 1, one 2, two 1s → \"111221\"). Return term n.
- 1 <= n <= 30
Intuition
The count and say sequence is defined by reading the previous term out loud. Term 1 is "1". You read that as "one 1", so term 2 is "11". You read that as "two 1s", giving "21", then "one 2, one 1" gives "1211", and so on. The task is to produce term n.
The first thing to accept is that there is no closed form. You cannot jump to term 30 without producing the 29 terms before it, because each term is defined purely in terms of its predecessor. So the algorithm is a loop, and the only real question is what happens inside one step.
That step is run-length encoding. Reading a string aloud means grouping consecutive identical digits and announcing how many of each: "111221" splits into the runs 111, 22, 1, which you say as "three 1s, two 2s, one 1" and write as "312211". Nothing more complicated is happening.
One thing worth knowing before you start:
- The strings grow quickly — roughly 30% longer each step, following Conway's constant λ ≈ 1.303577.
That growth is why n is capped at 30 in the problem constraints. It also tells you the cost is dominated by the length of the final string rather than by n itself, so building each term efficiently matters more than the loop overhead.
The count and say sequence is a simulation problem — there's no closed form, so the work is reading the spec exactly and running it n−1 times. The only real decision is how to group consecutive equal characters; a language's run-length grouping (groupby here) removes the manual counter and the off-by-one that comes with it.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(λⁿ) time and O(λⁿ) space.
Anchor the sequence at term 1
Start with the string "1". Every later term is derived from it, so this is the only value that has to be hard-coded. If n == 1, return it immediately without entering the loop.
Repeat the describe step n − 1 times
Term n is reached by applying the read-aloud transformation n − 1 times to the starting string. Wrap the encoding logic in a loop of that length, replacing the current string with its description on each pass.
Scan the string with a run pointer
Inside one describe step, walk the string with an index. At each position, note the character and advance a second pointer while it keeps repeating. The gap between the two pointers is the run length, which is the count you need to announce.
Emit count followed by digit
For each run, append str(count) + char to a list of pieces. Order matters — it is "three 1s", so the count precedes the digit. Collect the pieces in a list and join once at the end rather than concatenating strings in a loop, which in Python would make the step quadratic.
Jump the outer index past the run
After emitting a run, move the outer index to where the inner pointer stopped. Advancing by one instead is the classic bug — it would re-describe the same run repeatedly and produce nonsense. Each character is consumed exactly once per describe step.
Use groupby if the language offers it
Python's itertools.groupby performs run detection declaratively: iterate its output and emit the group length followed by the key. Same complexity, and it removes the two-pointer bookkeeping that the manual version has to get right.
Cost is driven by the final string length
Let L be the length of term n. Each describe step is linear in the string it reads, and lengths grow geometrically, so the total work is O(L) — dominated by the last term, with all earlier terms summing to a constant factor of it. Space is O(L) for the current and next strings.
Solution & live demo
Common pitfalls
Looping n times instead of n − 1
for _ in range(n):
s = ...s = "1"
for _ in range(n - 1):
s = ...The sequence starts at "1" for n = 1, so that term is the seed, not a computed step. Running the loop n times returns the (n+1)-th term.
Emitting digit-then-count
s = "".join(d + str(len(list(g))) for d, g in groupby(s))
s = "".join(str(len(list(g))) + d for d, g in groupby(s))
The rule is "say how many, then say which" — "21" means one 2 followed by one 1, giving "1211". Reversing the pair produces a different sequence entirely.
Counting all occurrences rather than consecutive runs
from collections import Counter counts = Counter(s)
for d, g in groupby(s):
...Counter collapses non-adjacent duplicates: "1211" would report three 1s, but the run-length reading is one 1, one 2, two 1s. Only consecutive equal characters form a group.
Edge cases
Loop runs zero times → "1".
Can't happen — no three equal consecutive digits ever appear in the sequence, and counts stay single-digit.