Problem statement

The count-and-say sequence starts at countAndSay(1) = "1". Each later term is produced by reading the previous term aloud: split it into runs of identical digits, then write each run as its length followed by its digit.

For example, "3322251" reads as two 3s, three 2s, one 5, one 1 — giving "23321511".

Given an integer n, return the n-th term.

Example 1

Input: n = 1
Output: 1

Example 2

Input: n = 4
Output: 1211
Explanation: 1 → 11 → 21 → 1211.

Example 3

Input: n = 6
Output: 312211

Constraints

• 1 <= n <= 22

Hints for Count and Say

1. Hint 1

   There is no closed form — build each term from the previous one.

2. Hint 2

   Scan the current term with two indices, extending the second while the digit stays the same.

3. Hint 3

   Append the run length and then the digit; do not reverse the two.

How to solve Count and Say

There is no closed form; generate each term from the previous by scanning runs of equal digits and writing count then digit.

Approach

1. Start from "1".
2. Repeat n - 1 times: walk the current term with i; extend j while cur[j] == cur[i]; append j - i and cur[i]; set i = j.
3. Return the final term.

Why it works

Reading a string aloud is exactly run-length encoding with the count written first, and the run scan produces one (count, digit) pair per maximal run.

Complexity

• Time — O(total length of the terms)
• Space — O(length of the n-th term)

Pitfalls

• Writing the digit before the count inverts the encoding.
• The terms grow roughly 30 % per step; strings, not ints, throughout.

Reference solution

Python

def countAndSay(n: int) -> str:
    cur = "1"
    for _ in range(n - 1):
        parts = []
        i = 0
        while i < len(cur):
            j = i
            while j < len(cur) and cur[j] == cur[i]:
                j += 1
            parts.append(str(j - i))
            parts.append(cur[i])
            i = j
        cur = "".join(parts)
    return cur

Java

public static String countAndSay(int n) {
    String cur = "1";
    for (int step = 2; step <= n; step++) {
        StringBuilder next = new StringBuilder();
        int i = 0;
        while (i < cur.length()) {
            int j = i;
            while (j < cur.length() && cur.charAt(j) == cur.charAt(i)) j++;
            next.append(j - i).append(cur.charAt(i));
            i = j;
        }
        cur = next.toString();
    }
    return cur;
}

C++

string countAndSay(int n) {
    string cur = "1";
    for (int step = 2; step <= n; step++) {
        string next = "";
        int i = 0;
        int len = (int) cur.size();
        while (i < len) {
            int j = i;
            while (j < len && cur[j] == cur[i]) j++;
            next += to_string(j - i);
            next += cur[i];
            i = j;
        }
        cur = next;
    }
    return cur;
}

JavaScript

var countAndSay = function(n) {
    let cur = "1";
    for (let step = 2; step <= n; step++) {
        let next = "";
        let i = 0;
        while (i < cur.length) {
            let j = i;
            while (j < cur.length && cur[j] === cur[i]) j++;
            next += String(j - i) + cur[i];
            i = j;
        }
        cur = next;
    }
    return cur;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium