Solve LeetCode 443 String Compression: Algorithm & Implementation

Understanding String Compression

String compression is essential for optimizing storage and transmission in real-world applications. LeetCode problem 443 challenges you to compress character arrays using specific rules: replace consecutive duplicates with the character followed by its count. Crucially, single characters remain unchanged without adding "1". After analyzing this problem, I've found most learners struggle with in-place modification and digit conversion.

Problem Rules and Examples

1. Consecutive characters: "aa" becomes "a2"
2. Single characters: "b" remains "b"
3. In-place modification: Overwrite original array
4. Return: New compressed length

Example:
Input: ["a","a","b","b","c","c","c"]
Output: 6 → Compressed array: ["a","2","b","2","c","3"]

Step-by-Step Algorithm

Two-Pointer Technique

1. Initialize write_index at 0 to track compressed position
2. Use i = 0 to traverse the array:

n = len(chars)
write_index = 0
i = 0

Character Processing Loop

while i < n:
    current_char = chars[i]
    count = 0
    # Count consecutive characters
    while i < n and chars[i] == current_char:
        count += 1
        i += 1

Compression Logic

Single Character Handling

if count == 1:
    chars[write_index] = current_char
    write_index += 1

Key Insight: Avoid unnecessary digits for single instances.

Multi-Character Compression

else:
    chars[write_index] = current_char
    write_index += 1
    # Convert count to string digits
    count_str = str(count)
    for digit in count_str:
        chars[write_index] = digit
        write_index += 1

Time Complexity Analysis

This approach runs in O(n) time with O(1) space. Each character is processed exactly once, and digit conversion depends only on count length (max 4 digits for LeetCode constraints).

Implementation in C++

int compress(vector<char>& chars) {
    int n = chars.size();
    int write_index = 0;
    
    for(int i = 0; i < n;) {
        char current = chars[i];
        int count = 0;
        
        while(i < n && chars[i] == current) {
            count++;
            i++;
        }
        
        chars[write_index++] = current;
        
        if(count > 1) {
            string count_str = to_string(count);
            for(char c : count_str) {
                chars[write_index++] = c;
            }
        }
    }
    
    return write_index;
}

Common Pitfalls and Solutions

1. Off-by-one errors: Use while loops instead of for to control index increments
2. Digit conversion: Remember to_string() for multi-digit counts
3. Edge cases:
   • Single character array: Returns 1
   • All unique characters: Returns original length
4. In-place modification: Test with ["a","b","b"] → Output: ["a","b","2"]

Advanced Optimization Tips

1. Early termination: If compressed length exceeds original, abort (though rare in LeetCode)
2. Group counting: Alternative approach with read/write pointers
3. Memory awareness: For production, consider input size constraints

Practice Recommendations

Actionable Checklist

1. Implement the solution without looking at code
2. Test with ["a","a","a","b","b","a","a"]
3. Time your solution against LeetCode's test cases
4. Modify to return compressed string (additional challenge)
5. Profile memory usage for large inputs

Recommended Resources

• Book: "Cracking the Coding Interview" (string manipulation section)
• Tool: LeetCode Playground for debugging
• Course: Udemy's "Data Structures & Algorithms" (specifically string modules)
• Community: LeetCode discussion boards for alternative solutions

Final Insights

String compression teaches fundamental pointer manipulation and in-place modification techniques. Practice shows that mastering this problem improves handling of related challenges like run-length encoding. The key is maintaining separate pointers for reading and writing while efficiently converting counts to strings.

"What edge case did you find most challenging when implementing this? Share your experience in the comments!"