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 <= 30Follow up: Could you solve it iteratively?
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.
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.
Time Complexity: O(2^n) as the length of the string grows exponentially.
Space Complexity: O(2^n) for storing the string.
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.
Time Complexity: O(2^n) as strings grow exponentially.
Space Complexity: O(2^n) due to storing strings and O(n) recursion stack.
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:
n - 1 times, iterating to generate the "Count and Say" sequence up to the nth term.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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(2^n) as the length of the string grows exponentially. |
| Recursive Approach | Time Complexity: O(2^n) as strings grow exponentially. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative String Simulation | O(n * L) | O(L) | Best general solution. Simple loop that builds each term sequentially with minimal overhead. |
| Recursive Construction | O(n * L) | O(n + L) | Useful when modeling the sequence definition directly or practicing recursion patterns. |
Count and Say | Made Super Easy | Simple Explanation | Leetcode 38 | codestorywithMIK • codestorywithMIK • 46,742 views views
Watch 9 more video solutions →Practice Count and Say with our built-in code editor and test cases.
Practice on FleetCode