Skip to main content
Talentd

Count and Say - Solution & Explanation

MediumString22 min readAsked at: Amazon, Microsoft, Meta +10
Practice this problem

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:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

Example 2:

Input: n = 1

Output: "1"

Explanation:

This is the base case.

 

Constraints:

  • 1 <= n <= 30

 

Follow up: Could you solve it iteratively?

Approach Overview

Problem Overview: Generate the nth term of the Count and Say sequence. Each term is created by reading the previous term and describing consecutive digits ("one 1", "two 1s", etc.), producing the next string.

Approach 1: Iterative String Simulation (O(n * L) time, O(L) space)

Build the sequence step by step starting from "1". For every iteration, scan the current string and group consecutive identical digits. Count how many times a digit repeats, append count + digit to a new string, then continue scanning. The key operation is a linear pass with two pointers (or an index and counter) to detect runs of the same character. If the length of the nth term is L, the total work is O(n * L) time with O(L) space for the constructed string.

This method is essentially string simulation. No advanced data structures are required—just careful iteration and string building. Problems involving sequence generation like this often fall under string manipulation and simulation. Iterative construction avoids recursion overhead and is straightforward to debug.

Approach 2: Recursive Construction (O(n * L) time, O(n + L) space)

Define the problem recursively: the nth term depends entirely on the (n-1)th term. First compute countAndSay(n-1), then run the same grouping logic over that returned string to build the nth result. The recursion depth is n, and each level processes a string of length L, so the time complexity remains O(n * L). Additional space comes from the call stack (O(n)) plus the generated string (O(L)).

This approach expresses the mathematical definition of the sequence directly. It pairs naturally with problems that involve repeated transformations of previous results, a pattern commonly discussed in recursion. The tradeoff is extra stack usage and slightly more overhead than the iterative loop.

Recommended for interviews: The iterative approach is typically expected. It shows you can simulate the process efficiently using a single pass through the string. Mentioning the recursive formulation demonstrates understanding of the sequence definition, but the iterative solution signals stronger control over space usage and implementation details.

Approach 1: Iterative Approach

This approach involves constructing the sequence iteratively. We start from the base case, which is '1', and iteratively build up the strings by counting and saying the digits from the last constructed string.

The solution initializes the result to '1'. For each iteration, it constructs the next sequence by reading the current result, counting contiguous digits, and forming a new string based on these counts. Memory is managed dynamically to accommodate changing string sizes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n) as the length of the string grows exponentially.
Space Complexity: O(2^n) for storing the string.

Try this approach in the editor →

Approach 2: Recursive Approach

The recursive approach defines the function countAndSay recursively by computing countAndSay(n-1), then generating the count-and-say encoding for it.

This method involves less memory usage on the function stack compared to an iterative approach but still leverages recursion for elegance.

The recursive C solution computes the sequence for n-1 and uses a helper function to calculate the next sequence by consecutively counting the digits in the current sequence.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n) as strings grow exponentially.
Space Complexity: O(2^n) due to storing strings and O(n) recursion stack.

Try this approach in the editor →

Approach 3: Simulation

The task requires outputting the appearance sequence of the n-th item, where the n-th item is the description of the n-1-th item in the sequence. Therefore, we iterate n-1 times. In each iteration, we use fast and slow pointers, denoted as j and i respectively, to record the current character's position and the position of the next character that is not equal to the current character. We then update the sequence of the previous item to be j-i occurrences of the current character.

Time Complexity:

  1. The outer loop runs n - 1 times, iterating to generate the "Count and Say" sequence up to the nth term.
  2. The inner while loop iterates through each character in the current string s and counts the consecutive occurrences of the same character.
  3. The inner while loop runs in O(m) time, where m is the length of the current string s.

Overall, the time complexity is O(n times m), where n is the input parameter representing the term to generate, and m is the maximum length of the string in the sequence.

Space Complexity: O(m).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHP

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(2^n) as the length of the string grows exponentially.
Space Complexity: O(2^n) for storing the string.

Recursive Approach

Time Complexity: O(2^n) as strings grow exponentially.
Space Complexity: O(2^n) due to storing strings and O(n) recursion stack.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative String SimulationO(n * L)O(L)Best general solution. Simple loop that builds each term sequentially with minimal overhead.
Recursive ConstructionO(n * L)O(n + L)Useful when modeling the sequence definition directly or practicing recursion patterns.

Video Solution

Count and Say | Made Super Easy | Simple Explanation | Leetcode 38 | codestorywithMIK • codestorywithMIK • 51,962 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count and Say easy or hard?
Count and Say is typically rated Medium because the logic requires careful grouping of consecutive characters while building new strings. The algorithm itself is straightforward, but off‑by‑one errors and incorrect group handling can make the implementation tricky.
Count and Say Python/Java solution
In Python or Java, iterate through the current string and count consecutive characters. When the character changes, append the count and the digit to a result string or StringBuilder. Repeat this process n-1 times starting from "1" to generate the nth term.
How to solve Count and Say in O(n)?
Strict O(n) time is not achievable because the output string grows with each iteration. The optimal approach is O(n * L), where you iterate n times and process the current string in a single pass. Each pass counts consecutive characters and appends count and digit pairs.
What is the best approach for Count and Say?
The iterative string simulation approach is the most practical solution. Start with "1" and repeatedly scan the current string to count consecutive digits, appending count and digit to form the next term. This runs in O(n * L) time where L is the length of the generated string and uses O(L) space.
Is Count and Say asked at Google/Amazon/Meta?
Count and Say appears in interview practice sets for companies like Amazon, Google, and Microsoft, though it is more commonly used as a warm‑up string problem. It tests the ability to simulate processes, handle consecutive groups, and manipulate strings efficiently.
What data structure is used in Count and Say?
The solution mainly uses string processing with counters. A loop scans the string while tracking the current character and its frequency, then appends the result to a new string or string builder. No complex data structures like hash maps or trees are required.
What is the time complexity of Count and Say?
Time complexity is O(n * L), where n is the requested term and L is the length of the final string. Each iteration scans the current string once to group consecutive digits and build the next string. Space complexity is O(L) for storing the generated term.

Ready to solve this problem?

Practice Count and Say with our built-in code editor and test cases.

Practice on FleetCode
Previous

Encode and Decode Strings

Next

String Compression