Count and Say
Understanding the Problem
Each term of this sequence describes the previous one. You start with "1", and to get the next term, you read the current term out loud. "1" is read as "one 1", which gives "11". Then "11" is read as "two 1s", giving "21", and "21" is read as "one 2, one 1", giving "1211".
Given n, the task is to generate the sequence term by term until you reach the nth one. The "reading" step is run-length encoding: scan the string, count consecutive identical characters, and build the next string from those counts and characters.
Key Constraints:
1 <= n <= 30- With n at most 30, we generate at most 30 terms. The string length grows by roughly 30% per term, but the 30th term is still only 4,462 characters, so direct simulation runs fast.- Every digit in every term is 1, 2, or 3, and no run of identical digits is ever longer than 3 (a proven property of the sequence). Run counts are always single digits, so a count can be appended as a single character.
Approach 1: Iterative Simulation
Intuition
Start with "1" and apply run-length encoding n - 1 times, the same way you would expand the sequence by hand.
Each pass scans the current string left to right with a pointer. At each run, count how many times the current character repeats, append the count and the character to a new string, then move the pointer past the run. After n - 1 passes, current holds the nth term.
Algorithm
- Initialize
current = "1"(the first term). - Loop
n - 1times to generate subsequent terms. - In each iteration, initialize an empty string
nextand a pointeri = 0. - While
iis within the string: - Record the character at position
i. - Count how many consecutive characters match it (advance
ifor each match). - Append the count and the character to
next. - Set
current = nextafter processing the entire string. - Return
current.
Visualization and Code
Loading animation...
- Time Complexity: O(n * L), where L is the length of the longest string generated. We loop n-1 times, and each iteration scans the entire current string once. For n=30, the longest string is 4,462 characters.
- Space Complexity: O(L). We store the current string and the next string being built, both proportional to L.
The same encoding step can also be written recursively, following the sequence's definition directly.
Approach 2: Recursive with StringBuilder
Intuition
The sequence is defined recursively: countAndSay(n) is the run-length encoding of countAndSay(n - 1). The code can follow that definition as written. The base case n = 1 returns "1", and the recursive case computes the previous term, then encodes it.
The time complexity is unchanged, and the recursion depth stays at most 30 because of the constraint on n, so stack overflow is not a concern. What changes is the structure: the control flow matches the definition instead of an explicit loop.
Algorithm
- Base case: if
n == 1, return "1". - Recursively compute
countAndSay(n - 1)to get the previous term. - Scan the previous term, counting runs of consecutive identical characters.
- Build the result by appending each count and character.
- Return the result.
Visualization and Code
Loading animation...
- Time Complexity: O(n * L). Same as Approach 1. We generate n terms, each requiring a single scan of the previous term.
- Space Complexity: O(n + L). The recursion stack holds up to n frames, but a frame allocates its strings only after its recursive call returns, and it returns immediately afterward. At any moment only a constant number of terms are live, so the strings contribute O(L) and the stack itself contributes O(n).
A third option keeps the iterative structure but replaces the hand-written counting loop with a regex that matches runs directly.
Approach 3: Iterative with Regex (Concise)
Intuition
The encoding step finds groups of consecutive identical characters, and a regex can express that grouping. The pattern (.)\1* matches a character followed by zero or more repetitions of itself, so each match is one complete run. For every match, append its length and its first character.
The algorithm and complexity are unchanged; the regex replaces the inner counting loop with a single pattern. The pattern relies on the backreference \1, which not every regex engine supports. Where backreferences are unavailable, or where there is no standard regex engine at all, the run grouping stays as a manual scan.
Algorithm
- Initialize
result = "1". - Loop
n - 1times. - In each iteration, use the pattern
(.)\1*to find all runs of consecutive identical characters. - For each match, take its length and its first character, and append both to the term being built.
- Set
resultto the new term. - Return
result.
Two languages cannot use that pattern. Go's RE2 engine and Rust's standard library have no backreferences, so \1 is unavailable. The Go version matches runs of each digit the sequence can contain instead, and the Rust version falls back to the manual scan from Approach 1.
Visualization and Code
Loading animation...
- Time Complexity: O(n * L). Same asymptotic complexity as the manual scanning approaches. The regex engine performs the same character-by-character scan as the manual loop.
- Space Complexity: O(L). We store the current string, the next string, and the list of regex matches, all proportional to L.