String Compression

Difficulty: Medium

Problem

Given an array of characters chars, compress it using the following algorithm: Begin with an empty string s. For each group of consecutive repeating characters in chars: if the group's length is 1, append the character to s; otherwise, append the character followed by the group's length. The compressed string s should not be returned separately, but instead be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars. After you are done modifying the input array, return the new length of the array.

Example

Input: chars = ["a","a","b","b","c","c","c"]
Output: 6, chars = ["a","2","b","2","c","3"]
Explanation: Groups are "aa", "bb", "ccc". Compressed: "a2b2c3". Return length 6.

Brute-force approach

Build a new compressed string first, then copy it back into the original array. Uses extra O(n) space for the intermediate string.

Steps

  1. Iterate through chars counting consecutive groups
  2. Build a new compressed list with chars and counts
  3. Copy the compressed list back into the original array
  4. Return the new length

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses O(n) extra space for the compressed list
  • Requires a copy-back step
  • Not truly in-place — the problem asks for in-place modification

Optimal approach

Key insight: The write pointer always lags behind (or equals) the read pointer, so we can safely overwrite without losing unread data.

Use two pointers: a read pointer to scan groups and a write pointer to overwrite the array from the front. Since compressed output is always ≤ original length, the write pointer never overtakes the read pointer.

Steps

  1. Initialize read = 0, write = 0
  2. While read < len: count group of identical chars
  3. Write the character at write position
  4. If count > 1, write each digit of the count
  5. Return write as the new length

Time complexity: O(n) · Space complexity: O(1)