Code Implementation

class Solution:
    def compress(self, chars):
        write = 0
        read = 0
        n = len(chars)
        while read < n:
            char = chars[read]
            count = 0
            # Count the number of occurrences of the current character
            while read < n and chars[read] == char:
                read += 1
                count += 1
            chars[write] = char
            write += 1
            if count > 1:
                for c in str(count):
                    chars[write] = c
                    write += 1
        return write
      

class Solution {
public:
    int compress(vector<char>& chars) {
        int write = 0, read = 0;
        int n = chars.size();
        while (read < n) {
            char current = chars[read];
            int count = 0;
            while (read < n && chars[read] == current) {
                read++;
                count++;
            }
            chars[write++] = current;
            if (count > 1) {
                string cnt = to_string(count);
                for (char c : cnt) {
                    chars[write++] = c;
                }
            }
        }
        return write;
    }
};
      

class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 0, n = chars.length;
        while (read < n) {
            char ch = chars[read];
            int count = 0;
            while (read < n && chars[read] == ch) {
                read++;
                count++;
            }
            chars[write++] = ch;
            if (count > 1) {
                String cnt = Integer.toString(count);
                for (char c : cnt.toCharArray()) {
                    chars[write++] = c;
                }
            }
        }
        return write;
    }
}
      

var compress = function(chars) {
    let write = 0, read = 0;
    const n = chars.length;
    while (read < n) {
        let char = chars[read];
        let count = 0;
        while (read < n && chars[read] === char) {
            read++;
            count++;
        }
        chars[write++] = char;
        if (count > 1) {
            let str = String(count);
            for (let c of str) {
                chars[write++] = c;
            }
        }
    }
    return write;
};
      

Problem Description

Given an array of characters chars, compress it in-place. The compression algorithm works as follows: For each group of consecutive repeating characters in the array, replace the group with a single character followed by the number of times it appears (if more than once). The compression must be done using only the input array for storage (no extra arrays), and the function should return the new length of the array after compression.

• Each group of consecutive repeating characters is replaced by the character and its count (if count > 1).
• The function must modify chars in-place and return the new length.
• Only constant extra space is allowed.
• Assume at least one valid solution exists for the input.

Example:
Input: ["a","a","b","b","c","c","c"]
Output: 6, and the array becomes ["a","2","b","2","c","3"].

Thought Process

To solve this problem, we first consider the brute-force approach: scan through the array, count consecutive characters, and build a new array with the results. However, the problem requires us to do this in-place, meaning we cannot use extra space proportional to the input size.

The key insight is to use two pointers: one for reading through the array (read), and one for writing the compressed characters (write). As we encounter a run of the same character, we count how many times it appears, then write the character (and its count, if >1) back to the array at the write position. This allows us to overwrite the input array as we go, using only constant extra space for counters and pointers.

By thinking in terms of "read" and "write" pointers, we avoid the need for extra storage and can meet the problem's constraints efficiently.

Solution Approach

• Initialize pointers: Set two pointers, read and write, both starting at 0.
• Iterate through the array: While read is less than the length of chars, do the following:
  • Store the current character and start counting its repetitions.
  • Advance read while the next character is the same, incrementing a count variable.
• Write compressed output:
  • Write the character at the write position, then increment write.
  • If count is greater than 1, convert count to a string and write each digit to the array, incrementing write each time.
• Continue until the end: Repeat the process for each group of characters.
• Return the result: The write pointer now indicates the new length of the compressed array.

This approach ensures that we only use constant extra space (for pointers and counters), and all modifications happen in-place.

Example Walkthrough

Let's use the sample input: ["a","a","b","b","c","c","c"].

1. First Group ("a"):
   • read scans two "a"s, so count=2.
   • Write "a" at write=0. Then write "2" at write=1.
2. Second Group ("b"):
   • read scans two "b"s, so count=2.
   • Write "b" at write=2. Then write "2" at write=3.
3. Third Group ("c"):
   • read scans three "c"s, so count=3.
   • Write "c" at write=4. Then write "3" at write=5.
4. End: write is now 6. The array is ["a","2","b","2","c","3"].

Each iteration compresses a group and writes the result in-place, overwriting the original array.

Time and Space Complexity

• Brute-force approach: O(n) time and O(n) space (if we used an extra array for the result).
• Optimized in-place approach: O(n) time and O(1) space.
  • Each character is read and written at most once.
  • Only a few variables are used for counters and pointers, so extra space is constant.

This makes the in-place two-pointer solution both efficient and scalable.

Summary

The string compression problem is elegantly solved using a two-pointer technique, allowing us to compress character groups in-place with constant extra space. By carefully tracking where to read and write in the array, we efficiently overwrite the input with its compressed form. The key insight is recognizing that a single pass, with careful pointer management, suffices to meet all constraints and optimize both time and space complexity.