0352MediumString

Run Report Lines

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A test rig prints one report line per cycle, and every line is a string of digits.

The first line printed is 1. Each later line is a description of the line before it: read that earlier line from left to right, break it into runs of equal digits, and for every run write how many digits the run held followed by the digit itself. Glue the pieces together in run order and that is the new line.

So the line after 1 is 11, because the earlier line held one 1. The line after 11 is 21, because that line held two 1 digits.

Return the line printed in cycle n.

Examples

Example 1

Input: n = 3
Output: "21"

Cycle 1 prints `1`. Cycle 2 describes it as one `1`, giving `11`. Cycle 3 describes `11` as two `1` digits, giving `21`.

Example 2

Input: n = 6
Output: "312211"

Cycle 5 prints `111221`, which holds three `1` digits, then two `2` digits, then one `1`, so cycle 6 prints `312211`.

Example 3

Input: n = 8
Output: "1113213211"

Cycle 7 prints `13112221`. Reading its runs gives one `1`, one `3`, two `1` digits, three `2` digits, then one `1`, which glues to `1113213211`.

Constraints

1 <= n <= 30

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_and_say(n: int) -> str:

Java

public String countAndSay(int n)

The intended approach

Time O(total length of lines 1 through n)Space O(length of line n)

There is no shortcut past the earlier lines, so produce them in order. For each line, walk it with two indices that bracket the current run of equal digits, and append the run length and the repeated digit to the pieces of the next line. Only the line just finished and the pieces of the line being built are held.

Pythonentry point: count_and_say

def count_and_say(n):
    # Build the lines in order.  For each line, walk it once, measure every run of
    # equal digits, and append the run length followed by the digit that repeated.
    # Time O(total length of lines 1..n); line 30 holds 4462 digits, and the lines
    # grow by roughly a quarter each step.  Space O(length of the longest line).
    line = "1"
    for _ in range(n - 1):
        pieces = []
        i = 0
        size = len(line)
        while i < size:
            j = i
            digit = line[i]
            while j < size and line[j] == digit:
                j += 1
            pieces.append(str(j - i))
            pieces.append(digit)
            i = j
        line = "".join(pieces)
    return line

The obvious version

Ask recursively for the previous line, then rebuild the current one by letting a regular expression pick out each maximal run of one repeated digit and writing its length and digit.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

import re


def bf_report_line(n):
    if n == 1:
        return "1"
    previous = bf_report_line(n - 1)
    out = ""
    for match in re.finditer(r"(\d)\1*", previous):
        chunk = match.group(0)
        out = out + str(len(chunk)) + chunk[0]
    return out

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See 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