#443 - String Compression

MediumArray / String

Given an array of characters chars, compress it in-place using the following algorithm: for each group of consecutive repeating characters, append the character followed by the group's length (if length > 1). Return the new length of the array after compression. You must use only O(1) extra space.

Input	Output
chars = ["a","a","b","b","c","c","c"]	6 | ["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"]

Solution Space

Try it

/**
 * Compresses a char array in-place with run-length encoding.
 * Uses a write pointer that always stays behind or at the read pointer,
 * so the compression never overwrites unread data.
 *
 * @param chars  Mutable array of single characters
 * @returns      New length of the compressed portion of chars
 */
export function compress(chars: string[]): number {
  let write = 0;
  let read = 0;

  while (read < chars.length) {
    const ch = chars[read];
    let count = 0;

    // Count consecutive identical characters
    while (read < chars.length && chars[read] === ch) {
      read++;
      count++;
    }

    // Write the character
    chars[write++] = ch;

    // Write the count digits (only if count > 1)
    if (count > 1) {
      const digits = String(count);
      for (const d of digits) {
        chars[write++] = d;
      }
    }
  }

  return write;
}

Approach: read/write two-pointer with run-length encoding – use a read pointer to count consecutive characters and a write pointer to update the array in-place.

Time: O(n) – each character is read exactly once.

Space: O(1) – compression is done in-place; only a few variables used.

#345 Reverse Vowels of a String

#605 Can Place Flowers