LeetCode 443 String Compression - Two Pointers (Med, Java, O(n))

• 443. String Compression

Algorithm Overview

The solution implements an in-place string compression algorithm using a two-pointer approach. Here's how it works:

• read: scans through the original characters
• write: tracks where to place the compressed output

Step-by-Step Breakdown

1. Initialize Pointers

int write = 0, read = 0;

Both pointers start at the beginning of the array.

2. Main Loop Structure

while (read < n) {
    char currentChar = chars[read];
    int count = 0;
    // ...
}

Continue until we've processed all characters.

3. Count Consecutive Characters

while (read < chars.length && chars[read] == currentChar) {
    count++;
    read++;
}

This inner loop counts how many times the current character repeats consecutively. The read pointer advances through all identical characters.

4. Write the Character

chars[write++] = currentChar;

Always write the character itself first, then increment the write pointer.

5. Write the Count (if > 1)

if (count > 1) {
    String countStr = String.valueOf(count);
    for (char c : countStr.toCharArray()) {
        chars[write++] = c;
    }
}

If the character appears more than once, convert the count to a string and write each digit individually.

Problem Solution

class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 0;
        int n = chars.length;
        while (read < n){
            char currentChar = chars[read];
            int count = 0;
            // count how many times currentChar repeats
            while (read<chars.length && chars[read] == currentChar) {
                count++;
                read++;
            }
            // write the character
            chars[write++] = currentChar;

            // if count>1, write its digits
            if (count>1) {
                String countStr = String.valueOf(count);
                for (char c: countStr.toCharArray()){
                    chars[write++] = c;
                }
            }
        }
        return write;
    }
}

Example Walkthrough

For input ['a','a','b','b','c','c','c']:

1. First iteration: currentChar = 'a', count = 2

   • Write 'a' at position 0
   • Write '2' at position 1
   • Result so far: ['a','2',...]

2. Second iteration: currentChar = 'b', count = 2

   • Write 'b' at position 2
   • Write '2' at position 3
   • Result so far: ['a','2','b','2',...]

3. Third iteration: currentChar = 'c', count = 3

   • Write 'c' at position 4
   • Write '3' at position 5
   • Final result: ['a','2','b','2','c','3']

The method returns write = 6, indicating the compressed length.

Key Insights

• In-place modification: The algorithm modifies the input array directly, saving space
• Two-pointer technique: Separating read and write operations prevents data corruption
• Handle multi-digit counts: Converting count to string handles cases where characters repeat 10+ times
• Time complexity: O(n) - each character is read once
• Space complexity: O(1) - only using a few extra variables

This approach efficiently compresses the string while maintaining the original array structure and returning the new length.