AlgoMaster Logo

String Compression

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

This is a run-length encoding problem with one extra requirement: we have to do the compression in-place, writing the result back into the same array we read from, using only constant extra space.

We group consecutive identical characters. For each group, we write the character itself, then write the count only if the group has more than one character. When the count is 10 or more, each digit of the count is written as a separate character, so a run of 12 b's becomes ['b', '1', '2'], not ['b', '12'].

The compressed output is always shorter than or equal to the original input. A single character stays length 1. A group of 2 becomes length 2 (character + "2"). A group of 3 or more always shrinks. This is what makes the in-place version possible: we can write the compressed result into the same array without ever overwriting characters we have not processed yet, as long as one pointer reads and another writes.

Key Constraints:

  • 1 <= chars.length <= 2000 → Performance is not the binding constraint here. The constant extra space requirement is, since it rules out building the result in a new array.
  • chars[i] can be lowercase, uppercase, digit, or symbol → Any character is valid, so the algorithm cannot assume the array contains only letters. Counts written as digits sit in the same array as the characters being counted.

Approach 1: Brute Force (Extra Space)

Intuition

Set the in-place requirement aside for a moment and build the compressed result in a separate list. Walk through the array, count each run of consecutive characters, and append the character (plus its count if greater than 1) to the result list. Then copy everything back into the original array.

This violates the O(1) space constraint, but it isolates the counting and digit-writing logic before we fold the read and write back into a single array.

Algorithm

  1. Initialize an empty list to hold the compressed result.
  2. Use a pointer i starting at index 0.
  3. While i is within bounds:
    • Record the current character.
    • Count how many consecutive characters match (advance i for each match).
    • Append the character to the result list.
    • If the count is greater than 1, convert it to a string and append each digit as a separate character.
  4. Copy the result list back into chars.
  5. Return the length of the result list.

Visualization and Code

Loading animation...

This is correct but uses O(n) extra space. Because the compressed output is never longer than the original, the result can go directly into the input array using two pointers, which removes the extra list.

Approach 2: Two Pointers In-Place (Optimal)

Intuition

Since the compressed form is never longer than the original input, we write the result directly into chars while reading from it, using two pointers. A read pointer scans the array to identify groups of consecutive characters, and a write pointer marks where the next compressed character goes.

The write pointer always stays at or behind the read pointer, so by the time we write to a position we have already read past it. That is what keeps the overwrite safe.

Algorithm

  1. Initialize a write pointer at 0 and a read pointer at 0.
  2. While read is within bounds:
    • Record the current character at chars[read].
    • Count consecutive occurrences by advancing read while the character matches.
    • Write the character at chars[write] and increment write.
    • If the count is greater than 1, convert it to a string, then write each digit character at successive write positions.
  3. Return write (the new length of the compressed array).

Visualization and Code

Loading animation...