Count and Say Problem in DSA Python

Mental Model

We describe a number by counting consecutive digits and saying what we see. Each step builds a new number from the previous one.

Analogy: Imagine reading a row of colored beads and saying aloud how many beads of each color you see in a row, then writing that down as the next row.

1 -> 11 -> 21 -> 1211 -> 111221 -> null
↑    ↑     ↑      ↑       ↑
start next  next   next    next

Dry Run Walkthrough

Input: start with '1', generate next 4 terms

Goal: build the sequence step by step by describing the previous term

Step 1: start with '1'

'1'

Why: This is the first term, the base to describe from

Step 2: read '1' as one 1 -> '11'

'11'

Why: We say 'one 1' so the next term is '11'

Step 3: read '11' as two 1s -> '21'

'21'

Why: We say 'two 1s' so the next term is '21'

Step 4: read '21' as one 2 then one 1 -> '1211'

'1211'

Why: We say 'one 2' then 'one 1' so the next term is '1211'

Step 5: read '1211' as one 1, one 2, two 1s -> '111221'

'111221'

Why: We say 'one 1', 'one 2', 'two 1s' so the next term is '111221'

Result:

'111221' is the 5th term in the sequence

Annotated Code

DSA Python

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'
        prev = self.countAndSay(n - 1)  # get previous term
        result = ''
        count = 1
        for i in range(1, len(prev)):
            if prev[i] == prev[i - 1]:
                count += 1  # count same digits
            else:
                result += f'{count}{prev[i - 1]}'  # say counted digits
                count = 1  # reset count
        result += f'{count}{prev[-1]}'  # say last counted digits
        return result

# Driver code
sol = Solution()
for i in range(1, 6):
    print(sol.countAndSay(i))

prev = self.countAndSay(n - 1) # get previous term

recursively get the previous term to describe

if prev[i] == prev[i - 1]: count += 1 # count consecutive same digits

count consecutive same digits

else: result += f'{count}{prev[i - 1]}' # say counted digits count = 1 # reset count

append count and digit to result and reset count

result += f'{count}{prev[-1]}' # say last counted digits

append the last counted digits after loop ends

Output

1

11

21

1211

111221

Complexity Analysis

Time: O(2^n) because each term roughly doubles in length from the previous term

Space: O(2^n) because we store the entire string for each term

vs Alternative: No simpler approach exists since each term depends on fully processing the previous term

Edge Cases

n = 1 (smallest input)

returns '1' immediately without recursion

DSA Python

if n == 1:
    return '1'

digits repeat multiple times in a row

counts all repeated digits correctly before saying

DSA Python

if prev[i] == prev[i - 1]:
    count += 1

When to Use This Pattern

When you see a problem asking to generate a sequence by describing the previous term's digits, use the Count and Say pattern to build each term from the last.

Common Mistakes

Mistake: Forgetting to append the last counted digits after the loop
Fix: Add a final append outside the loop for the last counted group

Mistake: Not resetting count when digit changes
Fix: Reset count to 1 inside the else block when digit changes

Summary

Generates a sequence where each term describes the count of digits in the previous term.

Use when asked to build a sequence by describing consecutive digits of the previous term.

The key is to count consecutive digits and then say the count followed by the digit to form the next term.