Skip to main content
Ace Hired
All coding problems

Count and Say

MediumstringsRun-length encodingstringsmediumrun-length-encoding

Maintained by Vikas D, software engineer

The sequence starts at "1". Every term after the first is created by scanning the previous term from left to right and describing what you read. You count how many times each digit repeats in a row, then write that count followed by the digit itself.

Take "21" as an example. Reading left to right you see one 2 followed by one 1, so you say "one 2, one 1", which you write down as "1211". That string becomes the next term, and you repeat the same reading process to get the one after it.

Your job is to return the term at position n. You are given only the integer n, and you generate every term from the first up to the nth by applying the read-and-describe rule one step at a time.

Each term only ever contains the digits 1, 2, and 3, because no digit can appear more than three times in a row once you follow the rule. The strings still grow quickly, so the work is in producing each term correctly rather than in any tricky math.

Examples

Input: n = 1
Output: "1"

The first term is defined as the string "1". There is nothing to read or transform.

Input: n = 4
Output: "1211"

Term 1 is "1", read as one 1 gives "11". "11" read as two 1s gives "21". "21" read as one 2 then one 1 gives "1211".

Input: n = 6
Output: "312211"

Term 5 is "111221". Reading it: three 1s, then two 2s, then one 1, which writes as "31" + "22" + "11" = "312211".

Constraints

  • 1 <= n <= 30
  • Every term is made up only of the digits 1, 2, and 3
  • Return the term as a string, not a number

Visible test cases

  • countAndSay(1) == "1"
  • countAndSay(2) == "11"
  • countAndSay(3) == "21"
  • countAndSay(4) == "1211"
  • countAndSay(5) == "111221"
  • countAndSay(6) == "312211"

Hints

Hint 1

There is no shortcut formula. You must build term 1, then term 2, and so on up to term n, because each term depends entirely on the one before it.

Hint 2

To turn one term into the next, walk through it once and find runs of the same digit. For each run, append the run length followed by the digit.

Hint 3

Use an inner pointer that skips past a whole run at a time instead of advancing one character per step, so each character is visited only once per term.

Loading the editor...

Approaches

Iterative run-length build

Time O(n * L) where L is the length of the longest term reached · Space O(L) to hold the current and next term

Start from "1" and apply the read-and-describe step n minus 1 times. Each step is a single left-to-right pass that groups consecutive equal digits and writes count plus digit.

  1. Initialise the current term as the string "1".
  2. Repeat the following n minus 1 times to advance one term per pass.
  3. Scan the current term with an index i. At each position read the digit, then count how many copies of it appear in a row.
  4. Append the count and the digit to a builder, then move i past the whole run.
  5. When the pass finishes, replace the current term with the freshly built string.
  6. After the last pass, return the current term.

Recursive definition

Time O(n * L) where L is the length of the longest term · Space O(n * L) including the recursion call stack

Express the term directly from its definition: term n is the run-length encoding of term n minus 1, with term 1 as the base case.

  1. If n equals 1, return "1".
  2. Otherwise compute the previous term by recursing on n minus 1.
  3. Run-length encode that previous string with the same single-pass grouping logic.
  4. Return the encoded result.

Common mistakes

  • Returning a number instead of a string. The answer can start with leading patterns that only make sense as text, so keep it a string throughout.
  • Forgetting to flush the final run. After the loop ends you still owe the count and digit for the last group of identical characters; handle the last run inside the loop by skipping the whole run, not after it.
  • Looping the wrong number of times. You apply the transform n minus 1 times, not n times, because term 1 is the starting point rather than a transform of something earlier.
  • Building the next term by repeatedly concatenating onto an immutable string in a hot inner loop, which can get slow. Collect parts in a list or builder and join once per pass.

Follow-up variations

  • Can you return only the length of the nth term without materialising the whole string? Discuss why the runs make this hard to do in closed form.
  • If asked for terms far beyond n = 30, what data type or streaming approach would you use as the strings get very large?
  • Could you generate the sequence lazily so a caller can pull one term at a time instead of computing a fixed n up front?
  • How would you prove that no digit ever appears four or more times in a row?

Recommended problems

Build the rest of your prep