Algorithm

Count and Say

Arrays & Strings Pattern

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.

CONSTRAINTS
  • 1 <= n <= 30
  • Every term is a string of digits
EXAMPLE 1
Input: n = 1
Output: "1"
The seed term defined by the sequence itself.
EXAMPLE 2
Input: n = 4
Output: "1211"
Reading forward: "1" → "11" → "21" → "1211". The 4th term reads "21" as one 2 and one 1.
EXAMPLE 3
Input: n = 5
Output: "111221"
Reading "1211" gives one 1, one 2, then two 1s → "11" + "12" + "21" = "111221".
Does 'say' mean spelling out words, or writing digits?
Digits. A run of one 2 becomes the two characters "12", and three 1s become "31" — never the English words.
Can I compute term n directly without building the earlier terms?
No. Each term is defined purely as a reading of the term before it, so there is no closed form to jump to — you must generate terms 1 through n in sequence.
How large can n get, and does the string blow up?
n goes up to 30. Term lengths grow by roughly Conway's constant (≈ 1.303) per step, so the 30th term is a few thousand characters — large but easily handled.

Generating the "Count and Say" sequence is like reading a string out loud. If you see the string "11", you say "two ones", which becomes "21". Each term is a literal description of the digits found in the previous term.

The Core Logic: Streak Counting

To generate the next term, we must translate a string like "1211" into its spoken description. The most reliable way is to walk through the string and count how many times the same character appears in a row (a "streak").

As soon as the character changes, we record the count and the digit we were just looking at, then reset our counter for the new digit.

Implementation: Iterative Simulation

We start with the base case "1" and repeat the "reading" process n-1 times. Using an iterative approach avoids recursion overhead and keeps the memory usage focused on the growing string.

python
res = "1"
for _ in range(n - 1):
    next_val = []
    i = 0
    while i < len(res):
        count = 1
        # Calculate the length of the current digit streak
        while i + 1 < len(res) and res[i] == res[i+1]:
            count += 1
            i += 1
        
        # Append "count" followed by the "digit"
        next_val.append(str(count) + res[i])
        i += 1
    res = "".join(next_val)
return res
Worked Example:n = 5 (Previous term: "1211")
0
1
i
1
2
2
1
3
1
We start at index 0 with the character '1'. Since the adjacent character at index 1 is different, our streak is one '1', which we record as '11'.
0
1
1
2
i
2
1
3
1
We move to index 1 and find the character '2'. The next character is different, so we record this streak of one '2' as '12'.
0
1
1
2
2
1
i
3
1
We move to index 2 and find the character '1'. Since the next character at index 3 is also '1', we increment our running streak to 2.
0
1
1
2
2
1
3
1
i
We reach the end of the string. We record the accumulated streak of two '1's as '21'. Joining our recordings ('11' + '12' + '21') yields the term '111221'.
Interactive Strategy Visualization

count & say

Iterative Transcription
term (n-1): "1211"
1
2
1
1
generating term (n): building...
Waiting to transcribe groups...
🔍

Generating the 5th term from the 4th term: "1211".

O(1.303ⁿ) Run-Length Simulation · Output-Bounded