Count and Say
A medium Strings interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Strings
- Sheets
- 1
- Core for
- 14 roles
The problem
Generate the nth term of the count-and-say sequence, where each term describes the previous term by counting consecutive groups of identical digits.
Example 1
- Input
- n=4
- Output
- "1211"
Example 2
- Input
- n=1
- Output
- "1"
Example 3
- Input
- n=5
- Output
- "111221"
Constraints
- 1 <= n <= 30
How to think about it
Updated 2026-09-29Every next sequence is a run-length encoding of the previous one. Group adjacent identical digits together into consecutive blocks, then emit the block's length followed by its digit. Because each step depends entirely on the full string representation of its predecessor, simulating step-by-step from base string '1' is the direct route.
Approaches, worst first
Recursive sequence generation
time O(m) · space O(m)
Define a recursive function where countAndSay(n) calls countAndSay(n - 1) and encodes its result. Every recursive step pauses execution on the call stack and produces intermediate strings, consuming stack frames without gaining any benefit over an iterative loop.
Iterative run-length compressionWrite this one
time O(m) · space O(m)
Start from '1'. Repeat n - 1 times: iterate across the current string with two pointers to find each contiguous span of matching characters, append count then character to a new string buffer, and replace the current string with the newly generated term.
Where people lose marks · 3
- Base case n = 1 must return '1', not an empty string or '11'.
- Trailing group omission: the final run of digits must be flushed into the builder when the loop reaches the end of the current string.
- String concatenation inside an inner loop causes quadratic memory churn in languages with immutable strings; accumulate tokens into an array or string builder.
The theory behind it
Strings — the ground this problem stands on. All Strings problems
What Strings is
A string is an ordered necklace of text characters, like letters printed along a ribbon of paper. Each character sits at an exact numeric slot, holding a glyph such as a letter, punctuation mark, or digit. In many programming languages, ribbons cannot be edited after creation, meaning changing a single character requires pressing an entirely new ribbon from scratch.
When to reach for it
Reach for string techniques when inputs consist of words, DNA sequences, serialized data formats, or sentences. Clues include questions testing palindromes, anagram matches, substring patterns, parenthesis balancing, or character frequency counts. Whenever an algorithm asks to transform capitalization, parse structured tokens, or compute edits between two phrases, string representations are the core subject.
How the pattern works
Think of characters as small integer codes ranging across standard character sets. Frequency tables with fixed sizes often replace heavy hash maps when tallying occurrences. For search tasks, maintain rolling state using character indices or sliding borders. When building output text through repeated appends, accumulate pieces inside a mutable list or string builder rather than concatenating strings directly, avoiding quadratic copy overhead.
More Strings problems
Target Roles
Core requirement for 14 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .