Problem of The Day: Count and Say

Problem Statement

leetcode problem link

Intuition

The problem is to generate the nth term in the “count and say” sequence. The sequence works by reading off the digits of the previous term, counting the number of digits in groups of the same digit. The first few terms are:

1
11 (one 1)
21 (two 1s)
1211 (one 2, then one 1)
111221 (one 1, one 2, two 1s)

The intuition is to build each term based on the previous one by counting consecutive identical digits and constructing a new string that represents that count followed by the digit.

Approach

We use a recursive helper function dfs(i, ans) to build the sequence up to the nth term:

• Base case: if i > n, we’ve reached the term after the nth one, so we return the final string by joining the characters in ans.
• When i == 1, we initialize the first term as "1".
• For all other i, we iterate through ans to construct the next term:
  • Use two pointers start and end to identify groups of the same digit.
  • When the digit changes, record the count (end - start) and the digit itself.
  • After the loop, append the final group’s count and digit.
• Replace ans with the new sequence and recurse to the next level.

Finally, the recursion builds up the sequence until the desired term is constructed and returned.

Complexity

• Time complexity:
  \(O(n \cdot m)\) where ( m ) is the average length of terms in the sequence up to ( n ). Each term’s length grows exponentially in worst cases, so time complexity may also be seen as exponential in ( n ).

• Space complexity:
  \(O(m)\) due to storing the current term in the ans list. Since we use recursion, additional stack space up to depth ( n ) is used as well.

Code

class Solution:
    def countAndSay(self, n: int) -> str:
        def dfs(i, ans):
            if i > n:
                return "".join(ans)
            if i == 1:
                ans.append("1")
            else:
                start, end = 0, 0
                temp = []
                for end in range(len(ans)):
                    if ans[start] != ans[end]:
                        temp.append(str(end - start))
                        temp.append(ans[start])
                        start = end
                temp.append(str(end - start + 1))
                temp.append(ans[-1])
                ans = temp[:]

            return dfs(i + 1, ans)

        return dfs(1, [])

Editorial

Approach 1: Straightforward

class Solution:
    def countAndSay(self, n: int) -> str:
        current_string = "1"
        for _ in range(n - 1):
            next_string = ""
            j = 0
            k = 0
            while j < len(current_string):
                while (
                    k < len(current_string)
                    and current_string[k] == current_string[j]
                ):
                    k += 1
                next_string += str(k - j) + current_string[j]
                j = k
            current_string = next_string
        return current_string

Approach 2: Regular Expression

class Solution:
    def countAndSay(self, n: int) -> str:
        s = "1"
        for _ in range(n - 1):
            # m.group(0) is the entire match, m.group(1) is its first digit
            s = re.sub(
                r"(.)\1*", lambda m: str(len(m.group(0))) + m.group(1), s
            )
        return s