Skip to main content

38. Count and Say

medium

Produce the n-th term in the count-and-say sequence, where each term describes the previous as 'count + digit' run-length encoding. Pure recursive construction on top of a string-scanning helper.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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". Note that in this problem, the run-length encoding is reversed: count then character. Given a positive integer n, return the n-th element of the count-and-say sequence.

Constraints

  • 1 <= n <= 30

Examples

Example 1

Input
n = 1
Output
"1"

Example 2

Input
n = 4
Output
"1211"

Explanation: countAndSay(1) = "1". countAndSay(2) = say "1" = one 1 = "11". countAndSay(3) = say "11" = two 1s = "21". countAndSay(4) = say "21" = one 2 + one 1 = "1211".

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recursive structure: countAndSay(n) = say(countAndSay(n - 1)).

Hint 2

Base case: n == 1 -> return "1".

Hint 3

say(s): scan s; for each run of the same digit, emit count + digit.

Hint 4

Iterative version: start with "1", apply say() n - 1 times.

Solution approach

Reveal approach

Two flavors. Recursive: countAndSay(n): if n == 1 return '1'; return say(countAndSay(n - 1)) where say(s) scans s left-to-right, counts each run of the same character, and emits (count + character). Iterative: result = '1'; for i in 2..n: result = say(result). Both run in O(n * L) time where L is the length of the final string (which grows exponentially in n — Conway's analysis shows L grows like ~1.3^n). Space matches the output length. Recursion depth is O(n).

Complexity

Time
O(n * L) where L = output length
Space
O(L)

Related patterns

  • recursion
  • string-processing
  • run-length-encoding

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Apple

Practice these live with InterviewChamp.AI

Drill Count and Say and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →