String Compression

You're given an array of single characters chars. Compress it by processing each run of consecutive equal characters:

• A run of length 1 becomes just the character.
• A longer run becomes the character followed by its length, with each digit of the length as its own array element. A run of 12 "m"s becomes ["m", "1", "2"].

Return the compressed array.

The classic version of this problem asks you to write the result into chars itself using O(1) extra space and return the new length. Here you return the compressed characters so they can be checked directly, but try to build them with the same in-place technique: the walkthrough shows how.

The output is never longer than the input. A run of length 1 writes one character; a run of length 2 writes two; a run of length 10 writes three. So as you scan left to right, the place you're writing can never get ahead of the place you're reading. That means you can compress into the same array you're reading from without overwriting anything you still need.

Use two pointers. read finds the end of the current run; write marks where the next compressed character goes. For each run, write the character, then, if the run is longer than one, write the digits of its length. When the scan ends, the first write slots hold the answer.

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

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

Point out the reason in-place writing is safe before you write the loop: the compressed form of any run is at most as long as the run, so write never passes read. That one sentence is what interviewers want to hear, because it's the difference between a guess and a proof.

Test out loud with a run of length 1, a run of exactly 10 (two digits), and a last run that ends at the array boundary.