Problem Statement in English

You’re given an integer n. The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

  • countAndSay(1) = "1"
  • countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string.

You’re asked to solve it it iteratively, and return the nth term of the count-and-say sequence.

Approach

This can be solved using a two-pointer approach. We will start with the first term of the sequence, which is “1”, and then iteratively generate the next terms until we reach the nth term.

Use a temporary string to build the next term by counting consecutive digits in the current term. For each group of consecutive digits, we append the count followed by the digit to the temporary string. After processing the entire current term, we update the current term to be the temporary string and repeat until we reach the desired term.

And we’re done!

Solution in Python


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

        while n:
            temp = ""
            l = 0
            N = len(curr)

            for r in range(1, N):
                if curr[l] != curr[r]:
                    temp += str(r - l) + curr[l]
                    l = r

            temp += str(N - l) + curr[l]

            curr = temp
            n -= 1

        return "".join(curr)

Complexity

  • Time: $O(n \cdot m)$
    where $n$ is the input integer and $m$ is the average length of the strings in the sequence. This is because we generate each term of the sequence iteratively, and for each term, we need to traverse the entire string to count consecutive digits.

  • Space: $O(m)$
    where $m$ is the average length of the strings in the sequence.

And we are done.