String Compression · Optimal Solution

Compress in place — two pointers, one pass.

A telemetry system compresses sensor logs by replacing runs of identical readings with a character and its count — 'aaabbc' becomes 'a3b2c1', but singletons omit the count. A read pointer races ahead to measure each run while a write pointer lags behind, recording the character and each digit of the count. In-place, one pass. O(n) time. O(1) extra space.

Interactive

Watch the read pointer scan and the write pointer compress

Concept

In-place run-length encoding

The algorithm partitions the array into two zones separated by the write pointer: the compressed prefix (final output) and the unprocessed suffix (still to be read). Because the compressed form is never longer than the original, the write pointer never overtakes the read pointer.

read pointer

Scans forward through each group of consecutive identical characters, counting how many there are before the value changes.

write pointer

Stays behind, writing the group character followed by the digit(s) of the count — but only when the count exceeds one.

safe overlap

The compressed encoding is always ≤ the original length, so writes never corrupt unread data. No auxiliary buffer is needed.

Algorithm

Scan runs, write character, write digits

  1. 1

    Initialize two pointers

    Set readIndex = 0 and writeIndex = 0. Both start at the beginning of the character array.

  2. 2

    Scan a run of identical characters

    Record the current character. Advance readIndex while the next character matches. The run length is readIndex − groupStart.

  3. 3

    Write the character and count

    Write the character at writeIndex. If the run length exceeds 1, convert it to a string and write each digit as a separate character.

  4. 4

    Return the new length

    After all groups are processed, writeIndex is the length of the compressed array. Characters beyond it are irrelevant.

Edge Cases

Where the pointers reveal the structure

All unique characters

Every run has length 1, so no count digits are written. The write pointer matches the read pointer step for step and the array remains unchanged.

Single character

With only one element, there is exactly one run of length 1. The algorithm writes the character and returns length 1. No digits are needed.

Multi-digit counts

A run of 12 identical characters produces digits '1' and '2', each occupying its own cell. The count is always decomposed into individual digit characters, never stored as a number.