38. Count and Say

Problem¶

Given n, return the nth term of the count-and-say sequence.

• countAndSay(1) = "1"
• Each next term is the run-length encoding of the previous one

Example:

n = 4
1 -> 11 -> 21 -> 1211
answer = "1211"

Run-length encoding (RLE) is a string compression method that works by replacing each maximal group of consecutive identical characters with the concatenation of the length of the group followed by the character itself. For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15", and replace "1" with "11". Thus the compressed string becomes "23321511".

Key trick¶

Build each term by scanning the previous string in runs of equal digits and converting each run into count + digit.

Trap¶

• Forgetting the base case n = 1
• Mixing up the order as digit + count instead of count + digit
• Repeated string concatenation in a way that is fine here but still easy to write incorrectly
• Overcomplicating it with recursion when simple iteration is enough

Why is it interesting?¶

It tests careful string scanning, iterative construction, and recognition of run-length encoding, which are common interview patterns.

Python solution¶

class Solution:
    def countAndSay(self, n: int) -> str:
        # Start from the first term and build the next one n - 1 times.
        s = "1"

        for _ in range(n - 1):
            parts = []
            i = 0

            # Run-length encode the current string.
            while i < len(s):
                j = i
                while j < len(s) and s[j] == s[i]:
                    j += 1
                parts.append(str(j - i))
                parts.append(s[i])
                i = j

            s = "".join(parts)

        return s

Comment on my solution¶

Your solution is correct.

• The recursive version is clear, but it recomputes prior terms through recursion and is less interview-friendly than the iterative version.
• The iterative version is the better answer here.
• One small improvement is to use a list of parts and "".join(...) instead of repeated rle += ..., which is cleaner and more efficient in Python.

## Solution
# WORKS - recursive
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        rle = ""
        cas = self.countAndSay(n - 1)
        i = 0
        while i < len(cas):
            ch = cas[i]
            count = 0
            while i < len(cas) and cas[i] == ch:
                count += 1
                i += 1
            rle += str(count) + ch
        return rle

Solution().countAndSay(4) # '1211'

# WORKS - iterative
class Solution:
    def countAndSay(self, n: int) -> str:
        rle = "1"
        for _ in range(2, n + 1):
            cas = rle
            rle = ""
            i = 0
            while i < len(cas):
                ch = cas[i]
                count = 0
                while i < len(cas) and cas[i] == ch:
                    count += 1
                    i += 1
                rle += str(count) + ch
        return rle