Skip to main content

38. Count and Say

medium

Generate the nth term of the count-and-say sequence: '1', '11', '21', '1211', '111221', '312211', ... Read each term aloud, encode the runs as count-digit pairs, and recurse. A classic run-length-encoding loop.

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". Given a positive integer n, return the nth element of the count-and-say sequence.

Constraints

  • 1 <= n <= 30

Examples

Example 1

Input
n = 4
Output
"1211"

Explanation: countAndSay(1) = "1". countAndSay(2) = RLE of "1" = "11". countAndSay(3) = RLE of "11" = "21". countAndSay(4) = RLE of "21" = "1211".

Example 2

Input
n = 1
Output
"1"

Explanation: Base case.

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

Iterative approach: start s = '1'. Repeat n - 1 times: compute the next term by run-length encoding s.

Hint 2

RLE: scan s; whenever the character changes (or end of string), append count + digit. Reset count.

Hint 3

Two pointers i and j: j scans through equal runs, i marks the start. After each run, append (j - i) and s[i]; advance i = j.

Hint 4

Sequence grows roughly like Conway's cosmological constant ~1.303^n — for n = 30, the length is in the tens of thousands. Use a string builder to keep allocation cheap.

Solution approach

Reveal approach

Iterative generation. Start s = '1'. Loop n - 1 times: build the next term using run-length encoding. Maintain two pointers — outer i starts at 0; inner j scans forward while s[j] == s[i]. When j hits a different character or the end, append (j - i) and s[i] to the next term, then set i = j. After processing all runs, replace s with the next term. After n - 1 iterations, return s. Use a string builder (or list with join) to avoid quadratic string concatenation. O(L_max) time where L_max is the length of the nth term (grows ~1.3^n, manageable for n <= 30). O(L_max) space.

Complexity

Time
O(n * m)
Space
O(m)

Related patterns

  • math
  • string-scan
  • run-length-encoding

Related problems

Asked at

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

  • Amazon
  • Apple
  • Facebook

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →