String Compression — Run-Length Encoding and the In-Place Two-Pointer Trick

Problem and Topic Statement#

String Compression (LeetCode 443) — given an array of characters chars, compress it using run-length encoding. Replace each group of repeated characters with the character followed by the group length (only if length is at least 2). Perform this in place using O(1) extra memory and return the new length.

Example: chars = ['a','a','b','b','c','c','c'] becomes ['a','2','b','2','c','3'], returning length 6. Numbers with multiple digits must be split across multiple cells: a run of 12 as becomes ['a','1','2'].

This question looks like a simple counter-and-write problem, but the in-place constraint and the multi-digit length splitting trip up most candidates. It is the canonical Amazon screen problem and a common Meta and Google warm-up.

Why This Topic Matters#

In-place transformations on arrays are a building block that appears across countless interview problems — Move Zeros, Remove Duplicates, Reverse Words, Rotate Array. The read-pointer plus write-pointer pattern is the universal answer, and String Compression is one of the cleanest examples that also exercises edge-case handling for multi-digit counts.

In production, run-length encoding is the simplest lossless compression algorithm. It powers PCX and BMP file formats, fax compression (CCITT Group 3 and 4), JPEG zigzag scan compaction, and column compression in databases like Redshift and ClickHouse. Knowing the algorithm is foundational for understanding how more complex schemes like LZ77 and Huffman coding extend it.

Algorithmically, the two-pointer pattern teaches a meta-skill: separating the iteration index (read) from the output index (write). This separation is the key to in-place mutation without auxiliary buffers. Once you internalise it, problems like LC 26 (Remove Duplicates), LC 27 (Remove Element), and LC 283 (Move Zeros) become trivial.

The Core Insight#

Use two pointers: read scans the input and write produces the output, both walking the same array. Because the compressed output is always at most as long as the input, the write pointer never overtakes the read pointer, so in-place mutation is safe.

Algorithm:

1. Initialise read = 0, write = 0.
2. While read lt n:
   • Mark the start of a run: start = read.
   • Advance read until the character changes.
   • Write chars[start] at chars[write]; increment write.
   • Compute count = read - start. If count is at least 2, convert it to its decimal digits and write each digit one cell at a time.
3. Return write.

The tricky part is multi-digit counts. A run of 12 as becomes the characters 'a', '1', '2'. You cannot write 12 as a single cell because each cell holds exactly one character. Convert the integer to a string and write character by character. In Python: str(count) is a four-line affair. In C/C++/Java with no helper, do it manually with division and an integer-to-character conversion.

Edge cases:

• Single-character runs write only the character with no count.
• Empty input returns 0.
• All same characters, e.g. all as, becomes ['a','length'].
• Runs of exactly length 1 do not emit a count digit.
• Counts greater than 99 produce three or more digit cells; the algorithm still works because the read pointer leads the write pointer.

The reason write never overtakes read: a run of length L either writes 1 cell (if L = 1) or 1 + digits(L) cells. Since digits(L) is at most log10(L) + 1, and 1 + log10(L) + 1 is at most L for L at least 2, writing is always behind reading.

Visual Dry Run / Worked Example#

Input: ['a','a','b','b','c','c','c']. Length 7.

read=0, write=0
  Run "aa" length 2.
  Write 'a' at write=0. write=1.
  Write '2' at write=1. write=2.
  read=2.
 
read=2, write=2
  Run "bb" length 2.
  Write 'b' at write=2. write=3.
  Write '2' at write=3. write=4.
  read=4.
 
read=4, write=4
  Run "ccc" length 3.
  Write 'c' at write=4. write=5.
  Write '3' at write=5. write=6.
  read=7.

Final array: ['a','2','b','2','c','3','c']. Return write = 6. The trailing c is ignored.

Multi-digit example: 12 as.

['a']*12  ->
read=0, write=0
  Run length 12.
  Write 'a' at 0. write=1.
  Convert 12 to "12". Write '1' at 1. write=2. Write '2' at 2. write=3.
  read=12.

Final: ['a','1','2', ... ]. Return write = 3.

Solution (Optimal)#

Python — Two pointers, in place#

def compress(chars):
    n = len(chars)
    read = 0
    write = 0
    while read < n:
        start = read
        while read < n and chars[read] == chars[start]:
            read += 1
        chars[write] = chars[start]
        write += 1
        count = read - start
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1
    return write

JavaScript — Two pointers#

function compress(chars) {
  const n = chars.length;
  let read = 0, write = 0;
  while (read < n) {
    const start = read;
    while (read < n && chars[read] === chars[start]) read++;
    chars[write++] = chars[start];
    const count = read - start;
    if (count > 1) {
      const str = String(count);
      for (const digit of str) chars[write++] = digit;
    }
  }
  return write;
}

Time complexity: O(n) — each cell is read once and written at most once. Space: O(1) extra (ignoring the digit conversion buffer of length at most about 10).

Variant — String compression for the LC 1531 hard version#

LC 1531 asks for the minimum length after deleting at most k characters from s and run-length-encoding the result. This is a 2D DP and not the same problem, but if asked, mention it. State: dp[i][k] = min compressed length of first i characters with k deletions. Transitions enumerate every group ending at i.

Common Mistakes#

• Allocating a new array. The problem demands O(1) extra memory; building a new list and copying it back violates the constraint.
• Writing the count as a single cell when it is multi-digit. A count of 12 must occupy two cells, '1' then '2', not the single number 12.
• Forgetting to skip count emission when count is 1. Singletons emit only the character.
• Off-by-one in the run scan. The inner loop advances read until the character changes; after the loop, read points at the first different character (or n).
• Returning the array instead of the new length. The problem expects the new length and mutated array; returning a sliced copy is wrong.
• Modifying chars while iterating with read already past the data. Once write advances past the original run, the original characters are gone, but the read pointer is always ahead, so this is fine. New candidates often think they need a buffer; they do not.

Interview Tips#

Lead with the two-pointer pattern. State explicitly that read and write walk the same array, that write never overtakes read, and that this is what makes in-place mutation safe. Many candidates do not articulate this; doing so demonstrates depth.

Walk through one example with a multi-digit count. Most failures happen because the candidate forgets that 12 is two cells. Showing this on the whiteboard pre-empts the bug.

Test the edge case of a singleton run: [a] returns 1 with no count. Also test the all-same case: [a,a,a] returns 2 with [a,3].

Mention that this is run-length encoding. Naming the canonical algorithm shows industry awareness and earns favourable signal.

Follow-up Questions#

1. What if the count can be larger than the alphabet allows? In binary RLE for fax, counts are capped at a max value; longer runs are split into multiple records.
2. Can you decode this in place? Generally no — decoding may expand the array, requiring a buffer or working from the end.
3. What if you can delete up to k characters first to maximise compression (LC 1531)? 2D DP over prefix length and deletions used.
4. How does RLE compare to Huffman or LZ77? RLE excels on data with long uniform runs; LZ77 generalises to arbitrary repeats; Huffman is bit-level entropy coding. Real compression schemes pipeline them — DEFLATE in PNG and ZIP runs LZ77 then Huffman.
5. Streaming variant: characters arrive one at a time. Maintain a running tally of the current run; flush when the character changes.

Key Takeaways#

• The read-pointer plus write-pointer pattern is the universal blueprint for in-place array transformations; String Compression is its cleanest exemplar.
• Multi-digit run counts must be written one digit per cell; treat the count as a string and copy character by character.
• Singletons emit only the character with no count digit; do not emit 1.
• Run-length encoding underlies BMP, PCX, fax, database column compression, and is the simplest building block of more complex schemes like DEFLATE.
• The in-place safety of two-pointer transformation rests on the invariant that write never overtakes read; verify this argument out loud during the interview.
• Generalisations like LC 1531 use 2D DP over prefix length and deletions; the underlying RLE structure is the same.