Count and Say
Count and Say is a medium arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (iterative run-length encoding), runs in O(L_1 + L_2 + … + L_n) time and O(L_n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recursion) up.
Problem
The count-and-say sequence is a list of digit strings. The first term is "1", and every later term is produced by reading the previous term aloud: split it into maximal blocks of the same digit, and for each block write how many digits it has followed by the digit itself.
For example, "3322251" is read as “two 3s, three 2s, one 5, one 1”, which becomes "23321511".
Given a positive integer n, return the n-th term of the sequence.
Examples
Example 1
- Input
n = 5- Output
"111221"- Why
- 1 → "one 1" = 11 → "two 1s" = 21 → "one 2, one 1" = 1211 → "one 1, one 2, two 1s" = 111221.
Example 2
- Input
n = 1- Output
"1"- Why
- The first term is defined as "1".
Example 3
- Input
n = 7- Output
"13112221"- Why
- Term 6 is "312211" (three 1s, two 2s, one 1), and reading it aloud gives one 3, one 1, two 2s, two 1s.
Constraints
1 <= n <= 30
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (recursion) | O(L_n · n) | O(L_n + n) |
| Optimal (iterative run-length encoding) | O(L_1 + L_2 + … + L_n) | O(L_n) |
1Brute force (recursion)
O(L_n · n)Every term up to n is scanned once; the terms grow roughly by a constant factor, so the total is dominated by the last few lengths.O(L_n + n)The recursion is n frames deep and the current term has length L_n.Follow the definition directly: term n is obtained by reading term n - 1 aloud. Recurse down to n = 1, then on the way back up turn each term into the next one by counting runs of equal digits.
- If n == 1, return "1".
- prev = countAndSay(n - 1).
- Scan prev; for each maximal block of equal digits append (block length, digit).
- Return the built string.
class Solution {
public String countAndSay(int n) {
if (n == 1) return "1";
String prev = countAndSay(n - 1);
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < prev.length()) {
int j = i;
while (j < prev.length() && prev.charAt(j) == prev.charAt(i)) j++;
sb.append(j - i).append(prev.charAt(i));
i = j;
}
return sb.toString();
}
}class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return "1"
prev = self.countAndSay(n - 1)
parts = []
i = 0
while i < len(prev):
j = i
while j < len(prev) and prev[j] == prev[i]:
j += 1
parts.append(str(j - i) + prev[i])
i = j
return ''.join(parts)class Solution {
public:
string countAndSay(int n) {
if (n == 1) return "1";
string prev = countAndSay(n - 1);
string out;
size_t i = 0;
while (i < prev.size()) {
size_t j = i;
while (j < prev.size() && prev[j] == prev[i]) j++;
out += to_string(j - i);
out += prev[i];
i = j;
}
return out;
}
};function countAndSay(n) {
if (n === 1) return "1";
const prev = countAndSay(n - 1);
let out = '';
let i = 0;
while (i < prev.length) {
let j = i;
while (j < prev.length && prev[j] === prev[i]) j++;
out += String(j - i) + prev[i];
i = j;
}
return out;
}2Optimal (iterative run-length encoding)
O(L_1 + L_2 + … + L_n)Each term is scanned exactly once to build the next one.O(L_n)Only the current and the next term are kept.Start from "1" and apply the reading step n - 1 times in a loop, using one string builder per step. It is the same work as the recursion but without the call stack, which is the simplest and most memory-friendly way to produce the term.
- cur = "1".
- Repeat n - 1 times: scan cur, counting the length of each run, and append count + digit to a new builder.
- Replace cur with the new string.
- Return cur.
class Solution {
public String countAndSay(int n) {
String cur = "1";
for (int step = 1; step < n; step++) {
StringBuilder next = new StringBuilder();
int count = 1;
for (int i = 1; i <= cur.length(); i++) {
if (i < cur.length() && cur.charAt(i) == cur.charAt(i - 1)) {
count++;
} else {
next.append(count).append(cur.charAt(i - 1));
count = 1;
}
}
cur = next.toString();
}
return cur;
}
}class Solution:
def countAndSay(self, n: int) -> str:
cur = "1"
for _ in range(n - 1):
nxt = []
count = 1
for i in range(1, len(cur) + 1):
if i < len(cur) and cur[i] == cur[i - 1]:
count += 1
else:
nxt.append(str(count))
nxt.append(cur[i - 1])
count = 1
cur = ''.join(nxt)
return curclass Solution {
public:
string countAndSay(int n) {
string cur = "1";
for (int step = 1; step < n; step++) {
string next;
int count = 1;
for (size_t i = 1; i <= cur.size(); i++) {
if (i < cur.size() && cur[i] == cur[i - 1]) {
count++;
} else {
next += to_string(count);
next += cur[i - 1];
count = 1;
}
}
cur = next;
}
return cur;
}
};function countAndSay(n) {
let cur = "1";
for (let step = 1; step < n; step++) {
const next = [];
let count = 1;
for (let i = 1; i <= cur.length; i++) {
if (i < cur.length && cur[i] === cur[i - 1]) {
count++;
} else {
next.push(String(count), cur[i - 1]);
count = 1;
}
}
cur = next.join('');
}
return cur;
}Edge cases to test
- n = 1 (no reading step at all)
- The last run of a term must also be written out
- Runs longer than 1, like "111"
Hints
Hint 1
Each term is the run-length encoding of the previous one: for every block of equal digits write its length, then the digit.
Hint 2
Group consecutive equal characters with a pointer that scans until the character changes.
FAQ
What is the best time complexity for Count and Say?
Optimal (iterative run-length encoding) runs in O(L_1 + L_2 + … + L_n) time and O(L_n) extra space. Each term is scanned exactly once to build the next one.
Which pattern does Count and Say use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).
Is there a brute force solution for Count and Say?
Yes. Brute force (recursion) takes O(L_n · n) time and O(L_n + n) space. Follow the definition directly: term n is obtained by reading term n - 1 aloud.
Which edge cases should I test for Count and Say?
n = 1 (no reading step at all); The last run of a term must also be written out; Runs longer than 1, like "111".