String Compression

How it works

We can compress the array in-place using two pointers: one for reading (i) and one for writing (k). Since the compressed form is never longer than the original (a character followed by its count takes at most as much space as the repeated characters), we can safely overwrite the array as we go. This eliminates the need for extra space.

Steps

1. Initialize k = 0 as the write pointer and i = 0 as the read pointer.
2. While i < n, write chars[i] at position k and increment k.
3. Use pointer j starting at i + 1 to find all consecutive characters equal to chars[i].
4. If the count j - i exceeds 1, convert it to a string and write each digit to chars[k++].
5. Move i to j and repeat.
6. Return k as the new length of the compressed array.

Complexity

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

Things to watch for

Forgetting to Write Multi-Digit Counts Character by Character

When the count of consecutive characters exceeds 9 (e.g., 12), you must write each digit separately ('1' then '2') rather than treating it as a single value. Failing to split the count into individual digit characters will produce incorrect output.

Writing Count for Single Characters

The problem specifies that you should only write the count if it is greater than 1. A common mistake is writing "a1" instead of just "a" for a single occurrence. Always check if (count > 1) before appending the count to the result.

Overwriting Unprocessed Characters in In-Place Solutions

When compressing in place, the write pointer can overwrite characters that haven't been read yet if not handled carefully. Since the compressed form is never longer than the original, this won't happen as long as you process groups completely before moving the write pointer forward.

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        n = len(chars)
        k = i = 0

        while i < n:
            chars[k] = chars[i]
            k += 1
            j = i + 1
            while j < n and chars[i] == chars[j]:
                j += 1

            if j - i > 1:
                for c in str(j - i):
                    chars[k] = c
                    k += 1
            i = j
        return k

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size(), k = 0, i = 0;

        while (i < n) {
            chars[k++] = chars[i];
            int j = i + 1;
            while (j < n && chars[i] == chars[j]) {
                j++;
            }

            if (j - i > 1) {
                string cnt = to_string(j - i);
                for (char c : cnt) {
                    chars[k++] = c;
                }
            }
            i = j;
        }

        return k;
    }
};