MediumStrings

Count and Say

1 approach, code in every language

The count-and-say sequence is built by describing the previous term out loud. The first term is the string "1". To create any later term, scan the previous term left to right, group consecutive identical digits together, and write down how many there are followed by the digit itself.

For example, "1" is spoken as "one 1" which becomes "11", and "11" is spoken as "two 1s" which becomes "21". Given a position n, return the n-th term of this sequence.

Example 1

Input: n = 1

Output: "1"

By definition the sequence starts with the string 1.

Example 2

Input: n = 4

Output: "1211"

The chain is 1 -> "11" -> "21" -> "1211", so the fourth term is 1211.

Constraints

1 <= n <= 30
Each term is generated only from the term directly before it

Iterative Run-Length Encoding

Begin with the seed string and rebuild the next term n-1 times by run-length encoding the current term.

Loading animation…

Intuition

Every term is simply the run-length encoding of the previous one: count how many times a digit repeats in a row, then emit that count followed by the digit. Because term k only depends on term k-1, we can start from the base string "1" and apply this encoding step repeatedly. Building iteratively avoids deep recursion and lets us reuse a single string that we grow, transform, and replace on each round until we reach the requested position.

Algorithm walkthrough

1Initialize the current term as the string "1".
2Repeat the following construction n-1 times to advance from term 1 to term n.
3Scan the current term, and for each group of equal adjacent digits count the run length.
4Append the run length followed by the repeated digit to a fresh builder for the next term.
5Replace the current term with the newly built string, and after all rounds return it.

Implementation

class Solution:
    def countAndSay(self, n: int) -> str:
        result = "1"
        for _ in range(n - 1):
            current = []
            i = 0
            while i < len(result):
                count = 1
                while i + 1 < len(result) and result[i] == result[i + 1]:
                    i += 1
                    count += 1
                current.append(str(count))
                current.append(result[i])
                i += 1
            result = "".join(current)
        return result

Time

O(n * m)

Space

O(m)

m is the length of the longest term produced; each term is scanned once to build the next.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Run Report Lines is our own problem on the technique behind Count and Say: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free