Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each term describes consecutive runs in the previous term: say the number of occurrences, then the digit. Equal digits separated by another digit must remain separate runs. For example, 111221 contains three ones, two twos, and one one, giving 312211.

Approach

Return "1" for the first term. Otherwise, recursively obtain term n - 1.
Start two pointers at the beginning of that string. Advance the right pointer while its character matches the run's first character.
Append the run length followed by its digit to the result.
Move the left pointer to the right pointer and repeat until every character has been consumed. Each character belongs to exactly one maximal run, so the concatenated descriptions are precisely the next term.

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'

        res = ''
        prev = self.countAndSay(n - 1)
        l = 0
        r = 0

        while l < len(prev):
            count = 0
            while r < len(prev) and prev[l] == prev[r]:
                count += 1
                r += 1
            res += str(count)
            res += prev[l]
            l = r

        return res

Complexity analysis

Let L_i be the length of the ith generated term. Because both implementations build each immutable term with repeated string +=, a safe worst-case time bound is O(Σ(i=1..n) L_i^2). The largest simultaneously live strings are the previous and current terms, and recursion keeps O(n) frames, so auxiliary space is O(L_(n-1) + L_n + n); the returned string has O(L_n) characters.