Show problems as
Classic problem #443MediumTwo PointersString

String Compression

Real-world version: Pack the Symbol Tape
Tracked in this browser only
Read String Compression on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstHashmaps · Strings, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def pack_tape(tape: list[str]) -> list:
Java
public List<Object> packTape(char[] tape)

More on the same topics