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)

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

Thinking Process

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

  1. Start with "1"
  2. For each subsequent term, scan the current string and group consecutive identical characters
  3. For each group, output (count)(digit)

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 {
public:
    string countAndSay(int n) {
        string curr = "1";
        for (int i = 2; i <= n; i++) {
            string next;
            for (int j = 0, k = 0; j < curr.size(); j = k) {
                while (k < curr.size() && curr[k] == curr[j])
                    k++;
                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

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 (to_string(k - j))
  • 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