1042MediumString

Shorthand for a Run of Marks

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 tape of lowercase letters reads tape. Write its shorthand by repeating the following until nothing is left of the tape: take off the longest stretch at the front made of one repeated letter, but never more than nine of it, and append to the shorthand how many were taken followed by that letter.

Return the shorthand.

Examples

Example 1

Input: tape = "aabbaa"
Output: "2a2b2a"

Three stretches of two letters each, so each is written as its count followed by its letter.

Example 2

Input: tape = "aaaaaaaaaa"
Output: "9a1a"

Ten of the same letter, but a stretch may hold at most nine, so nine come off first and the last one follows as a stretch of its own.

Example 3

Input: tape = "a"
Output: "1a"

A single letter is a stretch of one.

Constraints

1 <= tape.length <= 2 * 10^5
The tape is made of lowercase English letters.

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 compressed_string(tape: str) -> str:

Java

public String compressedString(String tape)

The intended approach

Time O(n) over the tape's length.Space O(n) for the shorthand.

Walk the tape once, carrying the letter of the stretch in hand and how many of it have been seen. On meeting a different letter, or on reaching nine of the same, write out what is held as a digit followed by the letter and begin a fresh stretch. The cap of nine is what keeps every piece of shorthand exactly two characters long, so nothing has to be measured or revisited after the fact. Whatever is still held when the tape runs out is written out the same way. One pass, and the shorthand only ever grows at its end.

Pythonentry point: compressed_string

def compressed_string(tape):
    out = []
    at = 0
    n = len(tape)
    while at < n:
        letter = tape[at]
        count = 0
        while at < n and tape[at] == letter and count < 9:
            count += 1
            at += 1
        out.append(str(count))
        out.append(letter)
    return "".join(out)

The obvious version

Follow the rule to the letter: keep what is left of the tape as a string of its own, measure the stretch at its front, append the piece of shorthand, and cut that stretch off the front before going round again. Costs a fresh copy of the remainder each time rather than a single walk.

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

def bf_compressed_string(tape):
    rest = tape
    out = ""
    while rest:
        letter = rest[0]
        take = 0
        while take < len(rest) and take < 9 and rest[take] == letter:
            take += 1
        out = out + str(take) + letter
        rest = rest[take:]
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 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