LeetCode 38: Count and Say

Problem Restatement

We are given a positive integer n.

We need to return the nth term of the count-and-say sequence.

The sequence starts with:

countAndSay(1) = "1"

For every n > 1, the next term is built by reading the previous term using run-length encoding.

Run-length encoding means grouping consecutive equal digits, then writing:

count + digit

For example:

"111221"

has groups:

"111", "22", "1"

So it becomes:

"31" + "22" + "11" = "312211"

The constraint is:

1 <= n <= 30

The problem statement defines the sequence recursively by countAndSay(1) = "1" and countAndSay(n) as the run-length encoding of countAndSay(n - 1).

Input and Output

Function shape:

def countAndSay(n: int) -> str:
    ...

Examples

Example 1:

n = 1

The first term is defined as:

"1"

Return:

"1"

Example 2:

n = 4

Build the sequence:

1: "1"
2: "11"
3: "21"
4: "1211"

Explanation:

"1"    -> one 1          -> "11"
"11"   -> two 1s         -> "21"
"21"   -> one 2, one 1   -> "1211"

Return:

"1211"

Example 3:

n = 5

The fourth term is:

"1211"

Read it as:

one 1, one 2, two 1s

So the fifth term is:

"111221"

First Thought: Simulate the Definition

The definition already tells us how to build the sequence.

Start from "1".

Then repeat n - 1 times:

1. Read the current string from left to right.
2. Group consecutive equal digits.
3. For each group, append the group length and the digit.
4. Replace the current string with the new string.

For example, from:

current = "3322251"

The groups are:

So:

"3322251" -> "23321511"

Key Insight

Each step is just a scan over the previous string.

We do not need recursion, and we do not need to store every term.

We only keep the current term.

To encode one term, use a pointer i.

At position i, find how far the current run of equal digits goes.

For example:

current = "111221"
           ^
           i

The digit is "1".

Move another pointer j until the digit changes.

"111221"
 ^^^
 i j

The run has length 3, so append:

"31"

Then continue from the next run.

Algorithm

Initialize:

current = "1"

Repeat n - 1 times:

1. Create an empty list parts.
2. Set i = 0.
3. While i < len(current):
   • Set j = i.
   • Move j while current[j] == current[i].
   • The count is j - i.
   • Append str(count) and current[i].
   • Set i = j.
4. Join parts into the next string.
5. Assign it back to current.

Return current.

Correctness

The sequence definition says that every term after the first is the run-length encoding of the previous term.

The algorithm starts with the correct first term, "1".

During one transformation, the inner loop partitions the current string into maximal consecutive groups of equal digits. For each group, it appends exactly the number of digits in that group followed by the digit itself. That is precisely the required run-length encoding.

After one iteration, current becomes the next term of the sequence. After n - 1 iterations, current has advanced from the first term to the nth term.

Therefore, the returned string is exactly countAndSay(n).

Complexity

For this problem, n <= 30, so direct simulation is sufficient.

Implementation

class Solution:
    def countAndSay(self, n: int) -> str:
        current = "1"

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

            while i < len(current):
                j = i

                while j < len(current) and current[j] == current[i]:
                    j += 1

                count = j - i
                parts.append(str(count))
                parts.append(current[i])

                i = j

            current = "".join(parts)

        return current

Code Explanation

Start from the first term:

current = "1"

We need to transform it n - 1 times.

for _ in range(n - 1):

Use a list instead of repeated string concatenation.

parts = []

The pointer i marks the start of the current run.

i = 0

The pointer j moves until the run ends.

while j < len(current) and current[j] == current[i]:
    j += 1

The run length is:

count = j - i

Append the count and the digit.

parts.append(str(count))
parts.append(current[i])

Then move to the next run.

i = j

After all runs are encoded, build the next term.

current = "".join(parts)

Return the final term.

return current

Testing

def check(n: int, expected: str) -> None:
    actual = Solution().countAndSay(n)
    assert actual == expected, (n, actual, expected)

def run_tests():
    check(1, "1")
    check(2, "11")
    check(3, "21")
    check(4, "1211")
    check(5, "111221")
    check(6, "312211")
    check(7, "13112221")

    print("all tests passed")

run_tests()

Test meaning: