Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count and Say

MEDIUMProblemSolveExternal Links

Description

The count-and-say sequence is a sequence of digit strings where each term is constructed by describing the previous term using run-length encoding.

The sequence begins with the string "1". To produce the next term, you read the current term aloud by grouping consecutive identical digits and stating the count of each group followed by the digit itself.

For example:

  • Term 1 is "1".
  • Reading "1" aloud: "one 1" → Term 2 is "11".
  • Reading "11" aloud: "two 1s" → Term 3 is "21".
  • Reading "21" aloud: "one 2, then one 1" → Term 4 is "1211".

More formally:

  • countAndSay(1) = "1"
  • countAndSay(n) is the run-length encoding of countAndSay(n - 1).

Run-length encoding (RLE) replaces consecutive identical characters with the count of those characters followed by the character itself. For instance, compressing "3322251" gives "23" + "32" + "15" + "11" = "23321511".

Given a positive integer n, return the nth term of the count-and-say sequence as a string.

Examples

Example 1

Input: n = 1

Output: "1"

Explanation: The first term of the count-and-say sequence is simply "1" by definition. This is the base case — there is no previous term to read aloud.

Example 2

Input: n = 4

Output: "1211"

Explanation: We build the sequence term by term:

  • countAndSay(1) = "1"
  • countAndSay(2) = RLE of "1" → read as "one 1" → "11"
  • countAndSay(3) = RLE of "11" → read as "two 1s" → "21"
  • countAndSay(4) = RLE of "21" → read as "one 2, then one 1" → "1211"

The 4th term is "1211".

Example 3

Input: n = 5

Output: "111221"

Explanation: Building on Example 2:

  • countAndSay(4) = "1211"
  • countAndSay(5) = RLE of "1211" → read as "one 1, one 2, two 1s" → "111221"

Notice how the group "11" at the end of "1211" produces "21" (two 1s) in the result, while the single characters '1' and '2' at the start each produce their own count-digit pairs.

Constraints

  • 1 ≤ n ≤ 30
  • The result string contains only digits '1', '2', and '3' (a proven mathematical property of the sequence when starting from "1").

Editorial

Brute Force

Intuition

The problem definition itself is recursive: term n depends on term n-1, which depends on term n-2, and so on, all the way down to term 1. This naturally suggests a recursive approach.

Imagine a chain of people in a line. The first person holds a card with "1" on it. The second person reads what the first person is holding — "one 1" — and writes "11". The third person reads the second person's card — "two 1s" — and writes "21". Each person depends on reading the previous person's card before they can write their own.

To get term n, we:

  1. Recursively ask for term n-1 (which in turn asks for term n-2, etc.).
  2. Once we have the previous term, we scan it left to right, grouping consecutive identical characters.
  3. For each group, we write down the count of the character followed by the character itself.
  4. This produces term n.

The core operation — scanning the previous string and producing a run-length encoded version — is the same regardless of which term we are building. The recursion simply automates the chain of dependencies.

Step-by-Step Explanation

Let's trace countAndSay(4) using the recursive approach:

Step 1: Call countAndSay(4). We need term 3 first, so we recurse.

Step 2: Call countAndSay(3). We need term 2 first, so we recurse again.

Step 3: Call countAndSay(2). We need term 1 first, so we recurse once more.

Step 4: Call countAndSay(1). Base case! Return "1".

Step 5: Back in countAndSay(2), we now have prev = "1". Scan it:

  • Character '1' appears 1 time consecutively.
  • Append "11" (count '1', then char '1').
  • Result: "11". Return "11".

Step 6: Back in countAndSay(3), we have prev = "11". Scan it:

  • Character '1' at index 0. Move to index 1: still '1'. Count = 2.
  • End of string. Append "21" (count '2', then char '1').
  • Result: "21". Return "21".

Step 7: Back in countAndSay(4), we have prev = "21". Scan it:

  • Character '2' at index 0. Move to index 1: '1' ≠ '2'. Count = 1.
  • Append "12" (count '1', then char '2'). Reset count for '1'.
  • Character '1' at index 1. End of string. Count = 1.
  • Append "11" (count '1', then char '1').
  • Result: "1211". Return "1211".

Recursive RLE — Building Term 4 from Term 3 — Watch how we scan the previous term "21" character by character, counting consecutive identical digits, and build the next term "1211".

Algorithm

  1. Base case: If n == 1, return "1".
  2. Recursive step: Call countAndSay(n - 1) to get the previous term prev.
  3. Initialize an empty result string and set count = 1.
  4. Scan prev from index 1 to the end:
    • If the current character equals the previous character, increment count.
    • Otherwise, append count (as a string) and the previous character to the result. Reset count = 1.
  5. Finalize: After the loop, append the count and last character of prev to the result.
  6. Return the result string.

Code

class Solution {
public:
    string countAndSay(int n) {
        // Base case: the first term is "1"
        if (n == 1) return "1";
        
        // Recursively get the previous term
        string prev = countAndSay(n - 1);
        
        string result = "";
        int count = 1;
        
        // Scan prev and group consecutive identical characters
        for (int i = 1; i < prev.size(); i++) {
            if (prev[i] == prev[i - 1]) {
                count++;
            } else {
                result += to_string(count) + prev[i - 1];
                count = 1;
            }
        }
        
        // Append the last group
        result += to_string(count) + prev.back();
        
        return result;
    }
};
class Solution:
    def countAndSay(self, n: int) -> str:
        # Base case: the first term is "1"
        if n == 1:
            return "1"
        
        # Recursively get the previous term
        prev = self.countAndSay(n - 1)
        
        result = []
        count = 1
        
        # Scan prev and group consecutive identical characters
        for i in range(1, len(prev)):
            if prev[i] == prev[i - 1]:
                count += 1
            else:
                result.append(str(count))
                result.append(prev[i - 1])
                count = 1
        
        # Append the last group
        result.append(str(count))
        result.append(prev[-1])
        
        return "".join(result)
class Solution {
    public String countAndSay(int n) {
        // Base case: the first term is "1"
        if (n == 1) return "1";
        
        // Recursively get the previous term
        String prev = countAndSay(n - 1);
        
        StringBuilder result = new StringBuilder();
        int count = 1;
        
        // Scan prev and group consecutive identical characters
        for (int i = 1; i < prev.length(); i++) {
            if (prev.charAt(i) == prev.charAt(i - 1)) {
                count++;
            } else {
                result.append(count).append(prev.charAt(i - 1));
                count = 1;
            }
        }
        
        // Append the last group
        result.append(count).append(prev.charAt(prev.length() - 1));
        
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(2^n)

Each term can be at most twice the length of the previous term (this happens when every character is different from its neighbor). In the worst case, the total work across all recursive calls is proportional to the sum of all term lengths: |term₁| + |term₂| + ... + |termₙ|. Since each term can double, this sum is bounded by O(2^n). In practice, for the count-and-say sequence starting from "1", the growth rate is approximately 1.3× per term (Conway's constant), but the upper bound remains O(2^n).

Space Complexity: O(n + 2^n)

The recursion stack uses O(n) frames (one per term from n down to 1). Additionally, we store the result string, which can be up to O(2^n) characters long for the nth term. The dominant term is O(2^n) for the string storage.

Why This Approach Is Not Efficient

The recursive approach works correctly but has notable downsides:

1. Recursion Stack Overhead: Each call to countAndSay(k) waits for countAndSay(k-1) to return before it can begin processing. This builds a call stack of depth n. While n ≤ 30 is small enough that stack overflow is unlikely, the overhead of maintaining n stack frames (each storing its own local variables and return address) is unnecessary.

2. String Creation at Every Level: Each recursive call creates a new string. When the recursion unwinds, intermediate strings (terms 1 through n-1) are created, used once to produce the next term, and then discarded. There is no reuse — each intermediate result exists solely to generate the next one.

3. No Practical Complexity Improvement, But Cleaner Execution: Both recursive and iterative approaches have the same O(2^n) time complexity because the core work — scanning and encoding each term — is identical. However, the iterative approach eliminates the recursion overhead entirely by building terms sequentially in a simple loop, making the code simpler, more memory-predictable, and easier to reason about.

The key insight is: since term k depends only on term k-1 (not on k-2, k-3, etc.), we do not need recursion. We can maintain a single "current term" variable, update it in place, and iterate from term 1 to term n.

Optimal Approach - Iterative RLE Generation

Intuition

Since each term depends only on the immediately preceding term, we can compute the sequence iteratively: start with "1" and repeatedly transform the current string into the next one until we reach term n.

Think of it like a factory conveyor belt. A card enters the machine with "1" printed on it. The machine reads the card, produces a new card with "11", and passes it back to the input. This card goes through the machine again to produce "21", which goes through again to produce "1211", and so on. We only ever need one card at a time — the current term — and we overwrite it each round.

The transformation step is identical to the recursive approach: scan the current string left to right, group consecutive identical characters, and for each group, write the count followed by the character. The only difference is organizational — instead of recursion, we use a simple for-loop from 2 to n.

This approach:

  • Eliminates recursion overhead (no call stack buildup).
  • Uses only O(1) extra space beyond the strings themselves (just loop variables and a counter).
  • Is straightforward to implement and debug.

Step-by-Step Explanation

Let's trace the iterative approach for n = 5:

Step 1: Initialize curr = "1" (term 1).

Step 2: Iteration i=2 — Transform "1" into term 2.

  • Scan "1": one group → character '1' with count 1.
  • Append "11". New curr = "11".

Step 3: Iteration i=3 — Transform "11" into term 3.

  • Scan "11": index 0 is '1', index 1 is '1' (same). Count = 2.
  • End of string. Append "21". New curr = "21".

Step 4: Iteration i=4 — Transform "21" into term 4.

  • Scan "21": index 0 is '2', count = 1.
  • Index 1 is '1' ≠ '2'. Append "12". Reset count = 1 for '1'.
  • End of string. Append "11". New curr = "1211".

Step 5: Iteration i=5 — Transform "1211" into term 5.

  • Scan "1211": index 0 is '1', count = 1.
  • Index 1 is '2' ≠ '1'. Append "11". Reset count = 1 for '2'.
  • Index 2 is '1' ≠ '2'. Append "12". Reset count = 1 for '1'.
  • Index 3 is '1' == '1'. Count = 2.
  • End of string. Append "21". New curr = "111221".

Step 6: Return "111221" as term 5.

Iterative RLE — Building Term 5 from Term 4 — Watch the iterative scan of "1211" as we count consecutive identical characters and build the next term "111221" character by character.

Algorithm

  1. If n == 1, return "1" immediately.
  2. Initialize curr = "1" (term 1).
  3. For each iteration i from 2 to n:
    a. Initialize an empty string next and set count = 1.
    b. Scan curr from index 1 to the end:
    • If the current character equals the previous character, increment count.
    • Otherwise, append count and the previous character to next. Reset count = 1.
      c. After the inner loop, append the final count and last character of curr to next.
      d. Set curr = next.
  4. Return curr.

Code

class Solution {
public:
    string countAndSay(int n) {
        string curr = "1";
        
        for (int i = 2; i <= n; i++) {
            string next = "";
            int count = 1;
            
            for (int j = 1; j < curr.size(); j++) {
                if (curr[j] == curr[j - 1]) {
                    count++;
                } else {
                    next += to_string(count) + curr[j - 1];
                    count = 1;
                }
            }
            
            // Append the last group
            next += to_string(count) + curr.back();
            curr = next;
        }
        
        return curr;
    }
};
class Solution:
    def countAndSay(self, n: int) -> str:
        curr = "1"
        
        for i in range(2, n + 1):
            next_term = []
            count = 1
            
            for j in range(1, len(curr)):
                if curr[j] == curr[j - 1]:
                    count += 1
                else:
                    next_term.append(str(count))
                    next_term.append(curr[j - 1])
                    count = 1
            
            # Append the last group
            next_term.append(str(count))
            next_term.append(curr[-1])
            curr = "".join(next_term)
        
        return curr
class Solution {
    public String countAndSay(int n) {
        String curr = "1";
        
        for (int i = 2; i <= n; i++) {
            StringBuilder next = new StringBuilder();
            int count = 1;
            
            for (int j = 1; j < curr.length(); j++) {
                if (curr.charAt(j) == curr.charAt(j - 1)) {
                    count++;
                } else {
                    next.append(count).append(curr.charAt(j - 1));
                    count = 1;
                }
            }
            
            // Append the last group
            next.append(count).append(curr.charAt(curr.length() - 1));
            curr = next.toString();
        }
        
        return curr;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

The iterative approach performs the same total work as the recursive one: for each term from 2 to n, we scan the entire previous term once. The length of each term can at most double compared to the previous term (when all characters are distinct neighbors). Therefore, the sum of all term lengths is bounded by 1 + 2 + 4 + ... + 2^(n-1) = O(2^n). In practice, with the standard starting seed "1", terms grow by a factor of roughly 1.3 (Conway's constant λ ≈ 1.3036), making the actual runtime much smaller than the worst-case bound.

Space Complexity: O(2^n)

We store two strings at any time: the current term curr and the next term being built next. The longest of these is the nth term, which can be O(2^n) characters. Unlike the recursive approach, there is no recursion stack — the loop uses only O(1) additional variables beyond the strings. This makes the space usage more predictable and eliminates the O(n) stack overhead.