0032MediumTwo PointersString

Pack the Symbol Tape

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 flight recorder writes one status symbol per cell into a fixed array tape, given here as a list of single-character strings. Before the tape is shipped off the aircraft, the firmware packs it down.

Packing rewrites every maximal stretch of one repeated symbol as the symbol itself, then the size of that stretch spelled out one digit per cell. A stretch of size 1 keeps the bare symbol with no size after it. A stretch of 12 equal symbols therefore takes three cells: the symbol, then 1, then 2.

The rewrite has to land inside tape, overwriting cells the firmware has already read, and may use only a constant amount of room besides tape itself. Symbols are case-sensitive, so b and B never belong to the same stretch.

Return a two-element list [length, prefix]. length is how many cells the packed tape occupies, and prefix is the list of those first length cells of tape after packing. Whatever sits beyond length is scratch and is never read back.

Examples

Example 1

Input: tape = ["T", "T", "G", "G", "G"]
Output: [4, ["T", "2", "G", "3"]]

Two Ts pack to `T 2` and three Gs pack to `G 3`, filling four cells; the fifth cell is left as scratch.

Example 2

Input: tape = ["P", "P", "P", "P", "Q", "R", "R", "R"]
Output: [5, ["P", "4", "Q", "R", "3"]]

The lone Q keeps no size after it, which is why the packed tape is five cells rather than six.

Example 3

Input: tape = ["K", "K", "K", "K", "K", "K", "K", "K", "K", "K", "K", "K"]
Output: [3, ["K", "1", "2"]]

The stretch is 12 long, so its size needs two cells, one per digit.

Constraints

1 <= tape.length <= 2000
Each tape[i] is a single character: an uppercase or lowercase English letter, a digit, or a punctuation symbol.
The packing must be done inside tape with O(1) extra room.

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 pack_tape(tape: list[str]) -> list:

Java

public List<Object> packTape(char[] tape)

The intended approach

Time O(n)Space O(1) extra

Run a read cursor and a write cursor over the same array. The read cursor swallows one whole stretch at a time and reports its symbol and size; the write cursor then lays down that symbol and, when the size exceeds one, each digit of the size as its own cell. The write cursor can never pass the read cursor because a stretch of size L costs at most 1 + digits(L) cells, which is at most L, so overwriting behind the reader is always safe.

Pythonentry point: pack_tape

def pack_tape(tape):
    n = len(tape)
    read = 0
    write = 0
    while read < n:
        symbol = tape[read]
        run = 0
        while read < n and tape[read] == symbol:
            read += 1
            run += 1
        tape[write] = symbol
        write += 1
        if run > 1:
            for digit in str(run):
                tape[write] = digit
                write += 1
    return [write, tape[:write]]

The obvious version

Group the tape with a grouping helper and append each symbol plus its spelled-out size to a brand new list, ignoring the in-place requirement entirely.

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_pack_tape(tape):
    from itertools import groupby
    packed = []
    for symbol, group in groupby(tape):
        run = len(list(group))
        packed.append(symbol)
        if run > 1:
            packed.extend(list(str(run)))
    return [len(packed), packed]

How this problem was checked

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