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 built by reading the previous string and describing consecutive digit groups (count followed by digit).
Approach 1: Iterative String Simulation (O(n * L) time, O(L) space)
Start from the base string "1". For each step from 2 to n, scan the current string and group consecutive identical digits. Count the length of each group and append count + digit to a new string. This is a classic string simulation pattern where you iterate once through the previous term and build the next one. If the current term length is L, generating the next term takes O(L) time, and repeating this for n iterations results in O(n * L) time with O(L) extra space for the next sequence.
This approach works well because every term depends only on the immediately previous term. You simply iterate through characters, track the current digit and its frequency, and flush the group when the digit changes. Problems like this fall under string processing and simulation techniques.
Approach 2: Recursive Construction (O(n * L) time, O(n + L) space)
The recursive version builds the sequence from the top down. Define countAndSay(n) as: if n == 1, return "1". Otherwise compute countAndSay(n-1) and transform that string by counting consecutive digits. The transformation logic is identical to the iterative scan, but recursion handles sequence generation. Each recursive call processes a string of length L, leading to O(n * L) total time.
Space usage includes the recursion stack plus the generated strings, so it becomes O(n + L). The recursion stack depth is at most n. This version highlights the natural definition of the sequence and is a good demonstration of recursion for sequence generation.
Recommended for interviews: The iterative simulation approach. Interviewers expect you to scan the string, count consecutive digits, and construct the next term using a builder or buffer. The recursive version shows the mathematical definition of the sequence, but iterative code is simpler, avoids stack overhead, and is easier to reason about in production systems.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n) as strings grow exponentially.
Space Complexity: O(2^n) due to storing strings and O(n) recursion stack.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative String Simulation | O(n * L) | O(L) | Best general solution. Simple loop through the previous string to build the next term. |
| Recursive Construction | O(n * L) | O(n + L) | Useful when modeling the sequence definition directly or practicing recursion patterns. |
Coding Interview Tutorial 28: Count and Say [LeetCode] • Amell Peralta • 31,482 views views
Watch 9 more video solutions →Practice Count and Say with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor