String Compression

The problem. Given an array of characters chars, compress it in place: replace every run of the same character with the character followed by the run's length — but a run of one is just the character. Lengths of 10 or more take one cell per digit. Return the new length; only that many cells at the front count.

Example

chars = ["a","a","b","b","c","c","c"]   ->  6, chars starts ["a","2","b","2","c","3"]
chars = ["a"]                           ->  1, ["a"]
chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
                                        ->  4, ["a","b","1","2"]   (12 takes two cells)

The idea: a read pointer and a write pointer

Scan the runs left to right. A read pointer moves over each run to measure it; a write pointer writes the compressed form back at the front of the same array. This is safe because the compressed form of a run is never longer than the run itself — "aa" becomes "a2", and "aaaaaaaaaaaa" (12) becomes "a12" — so write can never overtake read and overwrite characters that haven't been read yet.

1. Build a new string, then copy it back

1function compress(chars) {2  const parts = [];3  let i = 0;4  while (i < chars.length) {5    let j = i;6    while (j < chars.length && chars[j] === chars[i]) j++;   // chars[i..j-1] is one run7    parts.push(chars[i]);8    if (j - i > 1) parts.push(String(j - i));9    i = j;10  }11  const result = parts.join("");              // O(n) extra memory12  for (let k = 0; k < result.length; k++) chars[k] = result[k];   // copy back into chars13  return result.length;14}

Time O(n), space O(n). Correct and simple, but the problem asks for O(1) extra space, and the builder is as big as the output.

2. Read and write pointers, in place

1function compress(chars) {2  let write = 0, read = 0;3  while (read < chars.length) {4    const ch = chars[read];5    let run = 0;6    while (read < chars.length && chars[read] === ch) {   // measure the run of ch7      read++;8      run++;9    }10    chars[write++] = ch;                        // write the character once...11    if (run > 1) {12      for (const digit of String(run)) chars[write++] = digit;   // ...then its count, digit by digit13    }14  }15  return write;                                 // the compressed length16}

Time O(n), space O(1). read passes each character once and write writes each output cell once. Turning the count into digits costs O(log run) per run, which never exceeds the run's own length.

Comparing the approaches

The read/write pointer pair is one of the most reusable tricks for in-place array and string edits: Remove Duplicates, Move Zeroes and Remove Element all use it.

Edge cases to test

Variations