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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

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.

Two pointers 1 3 5 7 9 L R move L/R based on comparison

Approach: Iterative Simulation – O(n · 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;
    }
};

Solution Explanation

Approach: Two pointers on string (this problem)

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

How the code works:

  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)
    • j marks the start of a group
    • k advances while curr[k] == curr[j]
    • The run length is k - j

Walkthrough — input n = 4, expected output "1211":

countAndSay(1) = “1” countAndSay(2) = “11” — one 1 → “11” countAndSay(3) = “21” — two 1s → “21” countAndSay(4) = “1211” — one 2, one 1 → “1211”

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

References

Template Reference