Log inSign up
mediumLeetCodeNot Started

Count and Say

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on LeetCode
Lesson

Problem Statement

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).

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511".

Given a positive integer n, return *the nth element of the count-and-say sequence*.

Example 1 · Example:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2 · Example:

Input: n = 4
Output: "1211"
Explanation: countAndSay(1) = "1" countAndSay(2) = say "1" = one 1 = "11" countAndSay(3) = say "11" = two 1s = "21" countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Constraints:

  • 1 <= n <= 30

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the core string patterns underlying Count and Say.
  • Optimize time and space tradeoffs for string manipulation.
  • Handle string boundary conditions and unicode/ASCII edge cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Recursive or sequential series generation using Run-Length Encoding (RLE).
  • Iterating through consecutive duplicate character clusters.

Algorithmic Decision Tree:

  • Run-Length Compression and Expansion
  • Two Pointers Run Counting (curr != prev)

Connected Patterns:

String CompressionDecode StringEncode and Decode Strings

1. Recursive Generation with RLE Helper

Intuition

1. Base case: If n == 1, return "1". 2. Recursively get prev = countAndSay(n - 1). 3. Traverse prev counting consecutive identical characters, constructing the RLE string. 4. Return the newly constructed string.

When to apply: Natural mathematical implementation directly following the problem definition.

Algorithm

  1. If n == 1 return "1".
  2. Recurse to get previous string.
  3. Scan previous string for runs of identical characters.
  4. Append run length + character to result.
  5. Return encoded string.

Recursive Generation with RLE Helper

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 1, 1]
Current operationSTEP 1 OF 6
Observation: Base case $n = 1$ is predefined as '1'
Visual state
Values and pointers at this exact step
array
S
1
0
↑ BASE CASE: n=1
Variables at this step
n
1
result
1
callStackDepth
1
Check / comparison
countAndSay(1) = '1'.
Decision / next transition
Return base string '1' to recursion caller for n=2.
Why this step matters

Observation: Base case n = 1 is predefined as '1'.

Decision: Return '1' directly without running run-length encoding.

Invariant: The recursion terminates at n = 1 establishing the ground truth term.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string countAndSay(int n) {
7 if (n == 1) return "1";
8 std::string prev = countAndSay(n - 1);
9
10 std::string result = "";
11 int len = prev.size();
12 for (int i = 0; i < len;) {
13 int j = i;
14 while (j < len && prev[j] == prev[i]) {
15 j++;
16 }
17 result += std::to_string(j - i) + prev[i];
18 i = j;
19 }
20 return result;
21 }
22};
23
24int main() {
25 Solution sol;
26 std::cout << sol.countAndSay(1) << std::endl; // "1"
27 std::cout << sol.countAndSay(4) << std::endl; // "1211"
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^n) — Each iteration grows the string length by approximately a factor of 1.3 to 1.5 (asymptotically bounded by O(2n)).
  • Space complexity: O(n) call stack + O(2^n) output

Why Brute Force Doesn't Scale:

Naive brute force re-examines already processed substrings multiple times.

For N = 105, O(N2) requires 1010 operations (TLE), while O(N) finishes in < 10ms.

2. Iterative String Generation with Inner Single-Pass Counter

Intuition

1. Initialize curr = "1". 2. Loop step from 2 to n: - Maintain next = "" and count = 1. - Iterate through curr with pointer i. - If i + 1 < curr.length && curr[i] == curr[i + 1], increment count. - Otherwise, append count + curr[i], and reset count = 1. - curr = next. 3. Return curr.

When to apply: Eliminating recursion call stack overhead in iterative loops.

Algorithm

  1. Initialize current string to "1".
  2. Repeat n - 1 times in outer loop.
  3. Scan string, tracking count of matching consecutive characters.
  4. Append count and character to next string.
  5. Update current string.

Iterative String Generation with Inner Single-Pass Counter

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 1]
Current operationSTEP 1 OF 6
Observation: Initialize state variable curr = '1'
Visual state
Values and pointers at this exact step
array
S
2
1
0
↑ START curr = '1'
1
Variables at this step
i
1
curr
1
targetN
4
Check / comparison
Initialize curr = '1'. Loop i from 2 to n (4).
Decision / next transition
Iterative loop avoids recursive call stack overhead.
Why this step matters

Observation: Initialize state variable curr = '1'.

Decision: Execute (n - 1) iterations iteratively from i = 2 to 4.

Invariant: Iterative generation guarantees O(1) stack frames.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string countAndSay(int n) {
7 std::string curr = "1";
8
9 for (int k = 2; k <= n; ++k) {
10 std::string next = "";
11 int count = 1;
12 for (size_t i = 0; i < curr.size(); ++i) {
13 if (i + 1 < curr.size() && curr[i] == curr[i + 1]) {
14 count++;
15 } else {
16 next += std::to_string(count) + curr[i];
17 count = 1;
18 }
19 }
20 curr = next;
21 }
22
23 return curr;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::cout << sol.countAndSay(4) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(2^n) — Generates n strings, with the length of the nth string being approximately 1.3n: bounded by O(2n).
  • Space complexity: O(2^n)

3. Iterative Two-Pointer Run-Length Encoding

Intuition

1. Initialize curr = "1". 2. Repeat n - 1 times: - Create nextBuffer. - Set i = 0. - While i < curr.length: - Set j = i. - While j < curr.length && curr[j] == curr[i], j++. - Append (j - i) and curr[i] to nextBuffer. - i = j. - Set curr = nextBuffer. 3. Return curr.

When to apply: The definitive, production-optimized approach for generating sequence terms up to n = 30.

Algorithm

  1. Initialize curr = "1".
  2. Loop from 1 to n - 1.
  3. For current string, use two pointers i and j to find run boundaries.
  4. Append (j - i) and curr[i] to string builder.
  5. Update curr to new string builder content.
  6. Return curr.

Run-Length Encoding Iterative Expansion

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 1]
Current operationSTEP 1 OF 6
Observation: Previous term is "21"
Visual state
Values and pointers at this exact step
array
S
2
1
0
↑ i=0: char='2'
1
Variables at this step
prevTerm
21
currentChar
2
runLength
1
nextTermAccumulator
Why this step matters

Observation: Previous term is "21". Start run-length encoding at index 0: character is '2'.

Decision: Initialize run count = 1.

Invariant: Run length tracks consecutive duplicates of the current character.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string countAndSay(int n) {
7 std::string curr = "1";
8
9 for (int k = 1; k < n; ++k) {
10 std::string next;
11 int len = curr.size();
12 for (int i = 0; i < len; ) {
13 int j = i;
14 while (j < len && curr[j] == curr[i]) {
15 j++;
16 }
17 next += std::to_string(j - i);
18 next.push_back(curr[i]);
19 i = j;
20 }
21 curr = std::move(next);
22 }
23
24 return curr;
25 }
26};
27
28int main() {
29 Solution sol;
30 std::cout << sol.countAndSay(1) << std::endl; // Output: "1"
31 std::cout << sol.countAndSay(4) << std::endl; // Output: "1211"
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(2^n) — Processes each character in the current term in O(1) time. Length grows by factor of ~1.3 each step: O(2n) total.
  • Space complexity: O(2^n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Generation with RLE HelperO(2^n)O(n) call stack + O(2^n) outputRecursively compute countAndSay(n - 1), then apply a run-length encoding helper to produce the nth string.Time / space complexity limits.
2.Iterative String Generation with Inner Single-Pass CounterO(2^n)O(2^n)Iteratively generate strings from 1 to n in a loop, counting consecutive characters using a single lookahead condition.Time / space complexity limits.
3.Iterative Two-Pointer Run-Length EncodingOptimalO(2^n)O(2^n)Use an iterative two-pointer window (i and j) to measure run length j - i in a single contiguous block, appending directly to a mutable string buffer without intermediate string copies.Time / space complexity limits.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating the count as mathematical integer multiplication instead of string frequency grouping (e.g. "21" -> "one 2, one 1" -> "1211", NOT 2 * 1).

Pitfall 2:

Off-by-one errors when processing the final character run at the end of the string.

Pitfall 3:

Inefficient string concatenation in loops (str += char in languages without mutable string builders).

Crucial Edge Cases to Validate:

  • Empty string or single character string.
  • String with duplicate or repeating characters.
  • Strings with different lengths or extreme character bounds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify character constraints (lowercase English only vs full Unicode/ASCII).
  2. Explain your choice of data structure (array frequency map vs hash table) before coding.
  3. Walk through a concrete small example during the dry run.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time complexity for Count and Say?

Back to DSA Sheet