String Compression – 443. LeetCode

The “String Compression” problem requires reducing the size of a character array by compressing consecutive repeating characters into a single character followed by their count. For example, the [“a”, “a”, “b”, “b”, “b”, “c”] should be compressed to [“a”, “2”, “b”, “3”, “c”]. The challenge is to perform this compression in-place, which means modifying the original array without using extra space for another array. This problem encourages understand how to efficiently manage an array without additional memory overhead, making it ideal for practicing space optimization.

Brute Force

public String compressBruteForce(char[] chars) {
    StringBuilder compressed = new StringBuilder();
    int count = 1;

    for (int i = 1; i < chars.length; i++) {
        if (chars[i] == chars[i - 1]) {
            count++;
        } else {
            compressed.append(chars[i - 1]);
            if (count > 1) compressed.append(count);
            count = 1;
        }
    }

    // Add the last character and its count
    compressed.append(chars[chars.length - 1]);
    if (count > 1) compressed.append(count);

    return compressed.toString();
}

• Uses a StringBuilder to dynamically build the compressed result.
• It iterates through the array, counting consecutive duplicates.
• Whenever a different character is encountered, it appends the previous character and its count (if greater than 1) to the result.

This approach does not perform in-place compression and uses additional memory for the StringBuilder, which increases space complexity.

Optimal Algorithm and Data Structure

The two-pointer technique is well-suited for this problem:

1. First Pointer (i): Iterates through the array to count consecutive repeating characters.

2. Second Pointer (write): Tracks the position where compressed characters and counts should be written.

This approach allows us to compress the array in a single traversal, minimizing memory usage. We process each character group (e.g., ‘aaa’) by writing its compressed form directly in the array (‘a2’).

Why it works:

• We only need to remember the current character and its count, making the algorithm space-efficient.

• Writing compressed data during iteration ensures no extra space is required.

• Efficiency: The brute-force solution builds a new string, increasing memory usage. The two-pointer solution directly modifies the array, optimizing memory usage.

• Space Optimization: The use of in-place modification avoids auxiliary data structures, adhering to problem constraints.

Algorithm Steps

1. Initialize write to track the writing position and i to iterate through the array.

2. While i is less than the array length:

• Store the current character.

• Count consecutive occurrences of the character.

• Write the character at the write position.

• If the count is greater than 1, convert the count to characters and write them to the array.

3. Return write, which represents the new length of the compressed array.

public int compress(char[] chars) {
    int write = 0; // Pointer to write compressed characters
    int i = 0;     // Pointer to read characters
    
    while (i < chars.length) {
        char currentChar = chars[i];
        int count = 0;
        
        // Count the occurrences of the current character
        while (i < chars.length && chars[i] == currentChar) {
            i++;
            count++;
        }
        
        // Write the character
        chars[write++] = currentChar;
        
        // Write the count if greater than 1
        if (count > 1) {
            for (char c : String.valueOf(count).toCharArray()) {
                chars[write++] = c;
            }
        }
    }
    
    return write; // Return the length of the compressed array
}

Line By Line Explanations

1. Initialize State

int write = 0;
int i = 0;

• You’re starting with two markers:
• 1 (write): Where you’ll write the compressed strings.
• 2. (i): Current index to keep track of where you are in string.
• You need to keep track of where you’re reading and where to write the compressed strings

Step 2: Traverse String

while (i < chars.length) {

• Process all letters in the string

Step 3: Identify the Current String

char currentChar = chars[i];
int count = 0;

• You need to count consecutive occurrences of each letter and decide how to compress them.

Step 4: Count Consecutive Strings

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

• This step group similar string together and calculates how many there are in a row.

Step 5: Save Compressed String

chars[write++] = currentChar;

• This saves the string as the first part of the compressed entry.

Step 6: Add the Count (If Greater Than 1)

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

• This step ensures the compressed log format includes counts when needed.

Step 8: Return

return write;

• The write pointer now represents the size of the compressed string. This is useful because any leftover entries in the original log are no longer relevant.

The two-pointer technique is a powerful and versatile tool for solving in-place modification problems. By practicing this problem, you’ll build confidence in managing indices and processing arrays efficiently. Try similar problems, such as “Remove Element” or “Merge Sorted Array,” to solidify this pattern!