Pseudo-code:

text
function compress(chars):
    string res = ""
    i = 0
    while i < length(chars):
        char c = chars[i]
        count = 0
        while i < length(chars) and chars[i] == c:
            count++
            i++
        res += c
        if count > 1:
            res += string(count)
    
    for j from 0 to length(res):
        chars[j] = res[j]
    return length(res)

Why this fails: While this solution is logically correct and runs in linear time $O(N)$, it has a Space Complexity of $O(N)$ because it creates a separate string/list proportional to the size of the input. The problem explicitly constraints the solution to use O(1) constant extra space. Therefore, a brute force approach that allocates new storage for the compressed string is suboptimal and may be rejected in an interview setting.

Core Insight for String Compression

The core insight for solving LeetCode 443 efficiently lies in the realization that the compressed version of any character group is always shorter than or equal in length to the original group (with the exception of single characters, which remain length 1).

Because the compressed data is generated sequentially and is generally shorter than the source data, we can safely overwrite the beginning of the array with the compressed result while we are still reading the rest of the array.

The algorithm relies on maintaining a strict invariant:

1. Read Pointer (i): Scans the array to determine the extent of the current group of identical characters.
2. Write Pointer (write_index): Marks the position where the next piece of compressed data (character or digit) should be stored.

Visual Description: Imagine the array as a tape. The read head moves forward rapidly, counting how many times a character repeats. Once the read head hits a different character, the write head (which is lagging behind) records the character and the count. The write head then advances. Because we process groups from left to right, the write head will never overtake the read head, preventing data corruption.

Algorithm Strategy: Two Pointers - In-place Array Modification

To implement this strategy for String Compression, we follow these rules:

1. Initialize a write pointer at index 0.
2. Use a read pointer (often the loop variable i) to iterate through the array.
3. For every unique character group encountered by read:
   • Identify the start and end of the consecutive group to calculate the count.
   • Write the character itself to chars[write] and increment write.
   • If the count is greater than 1, convert the integer count into string format.
   • Iterate through the digits of the count string, writing each digit to chars[write] and incrementing write each time.
4. After the loop finishes, the write pointer represents the new length of the compressed array.

This approach ensures we satisfy the O(1) space constraint by utilizing the input array itself as the storage buffer.

Execution Flow

Let's trace the algorithm with chars = ["a", "a", "b", "b", "c", "c", "c"]:

1. Initialization: i = 0, write = 0.
2. First Group ('a'):
   • i points to first 'a'. We scan forward until we hit 'b' or end of array.
   • We find 2 'a's. count = 2.
   • Write 'a' at chars[0]. write becomes 1.
   • count > 1, so we convert 2 to "2". Write '2' at chars[1]. write becomes 2.
   • Move i past the group of 'a's.
3. Second Group ('b'):
   • i points to first 'b'. Scan forward.
   • We find 2 'b's. count = 2.
   • Write 'b' at chars[2]. write becomes 3.
   • count > 1, write '2' at chars[3]. write becomes 4.
   • Move i past the group of 'b's.
4. Third Group ('c'):
   • i points to first 'c'. Scan forward.
   • We find 3 'c's. count = 3.
   • Write 'c' at chars[4]. write becomes 5.
   • count > 1, write '3' at chars[5]. write becomes 6.
   • Move i past the group of 'c's.
5. Termination: i has reached the end of the array. Return write (which is 6).

The array effectively becomes ["a", "2", "b", "2", "c", "3", "c"], but since we return length 6, the consumer only sees the valid prefix.

Proof of Correctness

The correctness relies on the fact that write <= read at all times.

• Case 1 (Single Character): If a group has length 1 (e.g., ['x']), we write 'x' and advance write by 1. The read pointer also advances by 1. No overwrite occurs.
• Case 2 (Multiple Characters): If a group has length $k > 1$, we write 1 character plus $d$ digits, where $d$ is the number of digits in $k$. Since $k \ge 10^{d-1}$, the compressed length $1+d$ is always less than or equal to $k$ for $k \ge 2$.
  • Example: aa (len 2) -> a2 (len 2).
  • Example: aaaaaaaaaaaa (len 12) -> a12 (len 3).

Since the compressed form never exceeds the original length of the group, the write pointer never overtakes the start of the next unprocessed group. Thus, we never overwrite data that hasn't been read yet.

Reference Implementation

C++ Solution for LeetCode 443

cpp
#include <vector>
#include <string>

class Solution {
public:
    int compress(std::vector<char>& chars) {
        int write = 0;
        int i = 0;
        
        while (i < chars.size()) {
            char currentChar = chars[i];
            int count = 0;
            
            // Count consecutive characters
            while (i < chars.size() && chars[i] == currentChar) {
                i++;
                count++;
            }
            
            // Write the character
            chars[write++] = currentChar;
            
            // If count > 1, write the digits
            if (count > 1) {
                std::string countStr = std::to_string(count);
                for (char c : countStr) {
                    chars[write++] = c;
                }
            }
        }
        
        return write;
    }
};

Java Solution for LeetCode 443

java
class Solution {
    public int compress(char[] chars) {
        int write = 0;
        int i = 0;
        
        while (i < chars.length) {
            char currentChar = chars[i];
            int count = 0;
            
            // Count consecutive characters
            while (i < chars.length && chars[i] == currentChar) {
                i++;
                count++;
            }
            
            // Write the character
            chars[write++] = currentChar;
            
            // If count > 1, write the digits
            if (count > 1) {
                String countStr = Integer.toString(count);
                for (char c : countStr.toCharArray()) {
                    chars[write++] = c;
                }
            }
        }
        
        return write;
    }
}

Python Solution for LeetCode 443

python
class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0
        i = 0
        
        while i < len(chars):
            current_char = chars[i]
            count = 0
            
            # Count consecutive characters
            while i < len(chars) and chars[i] == current_char:
                i += 1
                count += 1
            
            # Write the character
            chars[write] = current_char
            write += 1
            
            # If count > 1, write the digits
            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1
                    
        return write