38. Count and Say

Reformulated question¶

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"

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 this question interesting?¶

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

Idiomatic 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

Pytest test cases¶

import pytest

@pytest.mark.parametrize(
    "n, expected",
    [
        (1, "1"),
        (2, "11"),
        (3, "21"),
        (4, "1211"),
        (5, "111221"),
        (6, "312211"),
        (7, "13112221"),
    ],
)
def test_count_and_say(n, expected):
    assert Solution().countAndSay(n) == expected

Comment on your 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