Author at SyntaxFlow
LeetCode 38, solved three ways — recursive, iterative, and an optimized iterative version — with intuition, C++ code, an animated dry run for each approach, and complexity analysis you can explain out loud.
⏱ 8 min read🧩 Strings · Recursion · Simulation🎯 Difficulty: MediumOn this page
Given a positive integern, return thenth term of the count-and-say sequence.
countAndSay(1) = "1", and every later term is the run-length encoding of the previous term — replace each maximal run of identical digits with "count followed by digit".Example: for n = 4:countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"To keep every approach grounded in the same example, we'll trace how each one produces "1211" from "21" — once through a recursive call stack, once through a plain iterative scan, and once through an optimized single-pass buffer.
The problem statement itself is a recurrence: countAndSay(n) depends on countAndSay(n-1). The most literal way to solve it is to translate that definition directly into a recursive function — call for the previous term, then run-length-encode whatever comes back.
It's the first working solution most people write, but two things make it the "brute" version here: it pays for a recursive call stack it doesn't need, and if you build the encoded result with plain string concatenation (result = result + ...), each concatenation silently creates a brand-new string object instead of extending one in place.
n == 1, return "1".countAndSay(n - 1) to get the previous term.count followed by the digit to the result by reassigning a new string (result = result + ...).string countAndSay(int n) {
if (n == 1) return "1";
string prev = countAndSay(n - 1); // recursive call
string result = "";
int i = 0;
while (i < (int)prev.size()) {
char ch = prev[i];
int count = 0;
while (i < (int)prev.size() && prev[i] == ch) {
count++;
i++;
}
// naive concatenation: builds a brand-new string every time
result = result + to_string(count) + string(1, ch);
}
return result;
}Approach 2 · Better
Since countAndSay(n) only ever needs the term right before it, there's no reason to recurse at all. Start from "1" and walk forward, run-length-encoding each term to produce the next one, stopping once you reach term n. This directly answers the problem's own follow-up: "could you solve it iteratively?"
current = "1".level from 2 to n.current left to right with two pointers, grouping consecutive identical digits and their counts.count then the digit to a fresh string next using += (in-place append, not full reconstruction).current = next and continue; after the loop, current is the answer.string countAndSay(int n) {
string current = "1";
for (int level = 2; level <= n; level++) {
string next = "";
int i = 0;
while (i < (int)current.size()) {
char ch = current[i];
int count = 0;
while (i < (int)current.size() && current[i] == ch) {
count++;
i++;
}
next += to_string(count); // in-place append
next += ch;
}
current = next;
}
return current;
}The iterative version is already solid, but two small inefficiencies remain: to_string(count) allocates a temporary string just to hold one digit, and rebuilding next from an empty string on every level can force multiple reallocations as it grows. Both are fixable with a fact specific to this sequence: a run of the same digit never has length greater than 3 (a known property of the look-and-say sequence), so the count is always a single digit — you can append it as a character directly, no to_string needed.
current = "1".reserve() capacity for next up front to avoid repeated buffer growth.current with two pointers exactly as before, but append the run count as '0' + count (a single character) instead of calling to_string.next into current with std::move to avoid an extra copy.n, then return current.string countAndSay(int n) {
string current = "1";
for (int level = 2; level <= n; level++) {
string next;
next.reserve(current.size() * 2); // avoid repeated reallocation
int i = 0;
int sz = (int)current.size();
while (i < sz) {
char ch = current[i];
int count = 0;
while (i < sz && current[i] == ch) {
count++;
i++;
}
next += char('0' + count); // runs never exceed 3, so this is safe
next += ch;
}
current = move(next);
}
return current;
}to_string().current string (as shown above) is already optimal on memory.n = 1 → return "1" directly, no scanning needed."111") → the two-pointer scan should still terminate cleanly at the string's end.i < size) are the most common bug — test with a term that ends mid-run.What is the Count and Say sequence?
It's a sequence where each term describes the previous term using run-length encoding, starting from the base term "1". Reading a term out loud — "one 1", "two 1s", "one 2 one 1" — literally produces the next term.
Which approach should I lead with in an interview?
Write the iterative bottom-up version as your primary solution since it directly answers the stated follow-up question, then mention the recursive version only to show you understand the recurrence, and bring up the buffer/allocation optimizations if asked to go further.
What is the time complexity of Count and Say?
Producing all n terms takes time proportional to n times the length of the longest term, since each term requires exactly one linear scan of the term before it.
Can a digit repeat more than 3 times in a row?
No — this is a known property of the look-and-say sequence. Because of it, a run's count is always a single digit, which is what makes it safe to append the count as one character instead of using a general integer-to-string conversion.
video link:
code link