38. Count and Say

Problem Statement

The count-and-say sequence is a sequence of digit strings defined by the recursive formula: countAndSay(1) = "1", and countAndSay(n) is the run-length encoding of countAndSay(n - 1). Given a positive integer n, return the nth element of the count-and-say sequence.

Examples

Example 1:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = "11"       — one 1 → "11"
countAndSay(3) = "21"       — two 1s → "21"
countAndSay(4) = "1211"     — one 2, one 1 → "1211"

Example 2:

Input: n = 1
Output: "1"

Constraints

  • 1 <= n <= 30

Clarification Questions

  1. Base case: What is the first term? (Assumption: countAndSay(1) = "1".)
  2. Encoding rule: How do we describe a string? (Assumption: Run-length encoding — consecutive same digits become (count)(digit).)
  3. Output type: Return a string? (Assumption: Yes, the nth term as a string.)
  4. n range: Any constraint on n? (Assumption: 1 <= n <= 30.)
  5. Digits: Only digits 1–9 in the sequence? (Assumption: Yes, from the recurrence.)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force (5 min) — Generate term 1, then term 2 from term 1 (scan and RLE), then term 3 from term 2, … up to term n. Straightforward simulation.

Step 2: Simulation with grouping (7 min) — For each term, scan the current string and group consecutive identical characters. For each group, append str(count) + digit to the next string. Use two pointers (start of group, end of group) for clean grouping.

Step 3: Optimized (8 min) — Same O(n · L) simulation; no better asymptotic. Focus on clean two-pointer grouping and correct string building. Edge case: n = 1 return "1" immediately.

Solution Approach

This is a pure simulation problem. Each term is generated by describing the previous term using run-length encoding.

Key Insights:

  1. Base case: Term 1 is "1".
  2. Recurrence: Term i = run-length encoding of term i - 1.
  3. Grouping: Use two pointers j (start of run) and k (past end of run); run length = k - j.
  4. Output: For each run, append str(k - j) + curr[j] to the next string.

Walk-Through

n=1: "1"
n=2: one 1        → "11"
n=3: two 1s       → "21"
n=4: one 2, one 1 → "1211"
n=5: one 1, one 2, two 1s → "111221"

Two-Pointer Grouping

The key technique is using two pointers j and k to identify each run of identical characters:

  • j marks the start of a group
  • k advances while curr[k] == curr[j]
  • The run length is k - j
  • After processing, jump j forward to k

This is cleaner than maintaining a separate counter variable.

Approach: Iterative Simulation – $O(n \cdot L)$

Build each term from the previous one, iterating from term 2 to term n. For each term, scan with two pointers to find consecutive groups.

class Solution:
def countAndSay(self, n):
    str curr = "1"
    for (i = 2 i <= n i += 1) :
    str next
    for (j = 0, k = 0 j < len(curr) j = k) :
    while k < len(curr)  and  curr[k] == curr[j]:
    k += 1
    next += to_string(k - j) + curr[j]
curr = next
return curr

Time: $O(n \cdot L)$ where $L$ is the length of the string at each step (grows roughly exponentially but bounded by n <= 30) Space: $O(L)$ for the current and next strings

Edge Cases:

  • n = 1: Return "1" without looping.
  • n = 2: From "1" we get one 1 → "11".

Common Mistakes:

  • Off-by-one on the loop: starting from i = 1 instead of i = 2 (since n = 1 is the base case).
  • Forgetting to convert the count to a string.
  • Using a single index with a counter variable instead of the cleaner two-pointer approach.

Key Takeaways

  • Run-length encoding is the core operation – group consecutive identical characters and describe them
  • The two-pointer grouping pattern (j = k after each group) is reusable in many string problems
  • This is a simulation problem – no clever trick needed, just clean implementation

Template Reference