String Compression

LeetCode 443: String Compression Solution & Explanation

Problem Overview

TL;DR: Iterate through the array using a read pointer to identify groups of consecutive characters and a write pointer to overwrite the array in-place with the compressed format.

The String Compression problem requires performing Run-Length Encoding on a character array. The task is to replace consecutive repeating characters with the character itself followed by the count of repetitions. If a character appears only once, it is appended without a count. Crucially, this operation must be performed in-place on the input array chars, and the algorithm must return the new length of the modified array.

This is a popular interview question (LeetCode 443) that tests a candidate's ability to manipulate array pointers efficiently under strict space constraints.

Brute Force Approach for String Compression

A naive approach to solving String Compression involves using auxiliary space to build the result.

1. Create a new empty string or list result.
2. Iterate through the input chars array.
3. Count consecutive occurrences of each character.
4. Append the character and its count (if greater than 1) to result.
5. Finally, copy the contents of result back into the original chars array and return the length.

Pseudo-code:

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.

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.

Pattern Reuse Notes

The Two Pointers - In-place Array Modification pattern is fundamental for optimizing space in array problems.

• LeetCode 26: Remove Duplicates from Sorted Array - Uses the same logic: a read pointer finds unique elements, and a write pointer builds the unique prefix.
• LeetCode 27: Remove Element - Skips specific values with the read pointer, compacting valid values with the write pointer.
• LeetCode 75: Sort Colors - A variation using three pointers to partition the array in-place.
• LeetCode 80: Remove Duplicates from Sorted Array II - Similar to problem 26 but allows a specific number of duplicates, requiring slightly more complex logic for the write pointer.

Reference Implementation

C++ Solution for LeetCode 443

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    int compress(std::vector<char>& chars) {
7        int write = 0;
8        int i = 0;
9        
10        while (i < chars.size()) {
11            char currentChar = chars[i];
12            int count = 0;
13            
14            // Count consecutive characters
15            while (i < chars.size() && chars[i] == currentChar) {
16                i++;
17                count++;
18            }
19            
20            // Write the character
21            chars[write++] = currentChar;
22            
23            // If count > 1, write the digits
24            if (count > 1) {
25                std::string countStr = std::to_string(count);
26                for (char c : countStr) {
27                    chars[write++] = c;
28                }
29            }
30        }
31        
32        return write;
33    }
34};

Java Solution for LeetCode 443

1class Solution {
2    public int compress(char[] chars) {
3        int write = 0;
4        int i = 0;
5        
6        while (i < chars.length) {
7            char currentChar = chars[i];
8            int count = 0;
9            
10            // Count consecutive characters
11            while (i < chars.length && chars[i] == currentChar) {
12                i++;
13                count++;
14            }
15            
16            // Write the character
17            chars[write++] = currentChar;
18            
19            // If count > 1, write the digits
20            if (count > 1) {
21                String countStr = Integer.toString(count);
22                for (char c : countStr.toCharArray()) {
23                    chars[write++] = c;
24                }
25            }
26        }
27        
28        return write;
29    }
30}

Python Solution for LeetCode 443

1class Solution:
2    def compress(self, chars: List[str]) -> int:
3        write = 0
4        i = 0
5        
6        while i < len(chars):
7            current_char = chars[i]
8            count = 0
9            
10            # Count consecutive characters
11            while i < len(chars) and chars[i] == current_char:
12                i += 1
13                count += 1
14            
15            # Write the character
16            chars[write] = current_char
17            write += 1
18            
19            # If count > 1, write the digits
20            if count > 1:
21                for digit in str(count):
22                    chars[write] = digit
23                    write += 1
24                    
25        return write