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.

Practice

1. What does the "Count and Say" sequence describe in simple terms?

easy

A. It sorts the digits of the previous term in ascending order.

B. It describes the count of digits followed by the digit itself in the previous term.

C. It reverses the digits of the previous term.

D. It adds 1 to each digit of the previous term.

Solution

1. Step 1: Understand the sequence rule

   The sequence reads the previous term by counting consecutive digits and saying the count followed by the digit.

2. Step 2: Apply the rule to a term

   For example, "1211" is read as "one 1, one 2, two 1s" which becomes "111221".

3. Final Answer:

   It describes the count of digits followed by the digit itself in the previous term. -> Option B

4. Quick Check:

   Count and Say = Count digits + Say digit [OK]

Hint: Remember: count digits, then say digit [OK]

Common Mistakes:

• Thinking it sorts digits instead of counting
• Assuming it reverses the sequence
• Adding numbers instead of counting

2. Which of the following is the correct Python syntax to start the Count and Say sequence with the first term as "1"?

easy

A. sequence = "1"

B. sequence = [1]

C. sequence = 1

D. sequence = (1)

Solution

1. Step 1: Identify the data type for sequence terms

   The terms are strings representing digits, so the first term should be a string "1".

2. Step 2: Check each option's data type

   sequence = "1" assigns a string "1", which is correct. sequence = [1] is a list, C is an integer, D is an integer in parentheses.

3. Final Answer:

   sequence = "1" -> Option A

4. Quick Check:

   Sequence term must be string "1" [OK]

Hint: Use string for digits, not int or list [OK]

Common Mistakes:

• Using integer 1 instead of string "1"
• Using list instead of string
• Using parentheses which do not create string

3. What is the output of the following Python code snippet for the 4th term of the Count and Say sequence?

def count_and_say(n):
    result = "1"
    for _ in range(n - 1):
        temp = ""
        i = 0
        while i < len(result):
            count = 1
            while i + 1 < len(result) and result[i] == result[i + 1]:
                i += 1
                count += 1
            temp += str(count) + result[i]
            i += 1
        result = temp
    return result

print(count_and_say(4))

medium

A. 1211

B. 111221

C. 21

D. 312211

Solution

1. Step 1: Trace the sequence terms up to n=4

   Term 1: "1"; Term 2: "11" (one 1); Term 3: "21" (two 1s); Term 4: "1211" (one 2, one 1).

2. Step 2: Confirm output of count_and_say(4)

   The function returns "1211" for n=4 as reasoned above.

3. Final Answer:

   312211 -> Option D

4. Quick Check:

   4th term = 312211 [OK]

Hint: Write terms stepwise: 1, 11, 21, 1211, 111221, 312211 [OK]

Common Mistakes:

• Confusing term 3 and 4 outputs
• Miscounting repeated digits
• Mixing digits order in output

4. The following code attempts to generate the Count and Say sequence but has a bug. What is the error?

def count_and_say_bug(n):
    result = "1"
    for _ in range(n):
        temp = ""
        i = 0
        while i < len(result):
            count = 1
            while i + 1 < len(result) and result[i] == result[i + 1]:
                count += 1
            temp += str(count) + result[i]
            i += 1
        result = temp
    return result

print(count_and_say_bug(4))

medium

A. Returns empty string always

B. Syntax error because of missing colon

C. Infinite loop due to missing i increment inside inner while loop

D. Index out of range error

Solution

1. Step 1: Analyze the inner while loop

   The inner while loop increments count but does not increment i, causing infinite loop when consecutive digits match.

2. Step 2: Identify missing increment

   To fix, add i += 1 inside the inner while loop to move forward.

3. Final Answer:

   Infinite loop due to missing i increment inside inner while loop -> Option C

4. Quick Check:

   Missing i++ in inner loop causes infinite loop [OK]

Hint: Check all loops increment their counters properly [OK]

Common Mistakes:

• Forgetting to increment loop variable inside nested loops
• Assuming syntax error without checking logic
• Ignoring infinite loop possibility

5. Given the Count and Say sequence starting with "1", what is the 6th term in the sequence?

hard

A. 312211

B. 13112221

C. 1113213211

D. 1211

Solution

1. Step 1: List terms up to 6th

   Term 1: "1"; Term 2: "11"; Term 3: "21"; Term 4: "1211"; Term 5: "111221"; Term 6: "312211".

2. Step 2: Confirm 6th term matches option

   312211 "312211" matches the 6th term as derived.

3. Final Answer:

   312211 -> Option A

4. Quick Check:

   6th term = 312211 [OK]

Hint: Write terms stepwise to avoid confusion [OK]

Common Mistakes:

• Mixing up 5th and 6th terms
• Skipping terms or misreading counts
• Choosing longer terms incorrectly