Leetcode 443

String Compression – LeetCode Solution in Java

Problem Overview

Given an array of characters chars, compress it in place using the following rules:

• If a character appears only once consecutively, keep it as it is.

• If a character appears multiple times consecutively, replace the group with the character followed by its frequency.

• If the frequency is 10 or greater, write each digit separately.

• The compressed string must be stored in the original array. Do not create a separate array for the result.

Return the length of the compressed string.

Example 1

Input:

chars = ["a","a","b","b","c","c","c"]

Output:

5

Explanation:

The compressed array becomes:

["a","2","b","2","c","3"]

The compressed string is a2b2c3, and its length is 6.

Example 2

Input:

chars = ["a"]

Output:

1

Explanation: The character appears only once, so no compression is required.

Example 3

Input:

chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:

4

Explanation: The compressed string is ab12, which has a length of 4.

Approach: Two Pointers

We can solve this problem efficiently using two pointers:

• i: Tracks the beginning of the current group of consecutive characters.

• res: Tracks the position where the compressed result should be written.

The key observation is that the compressed result never occupies more space than the original array. Therefore, we can safely overwrite the original array without creating another array.

Algorithm

1. Initialize i = 0 and res = 0.

2. Traverse the array while i is less than its length.

3. Store the current character and count its consecutive occurrences.

4. Write the character at chars[res] and increment res.

5. If the group contains more than one character, convert its count to a string and write each digit into the array.

6. Move i to the beginning of the next group.

7. Return res, the length of the compressed string.

Java Solution

class Solution {
    public int compress(char[] chars) {
        int i = 0;
        int res = 0;

        while (i < chars.length) {
            char currentChar = chars[i];
            int groupLength = 0;

            // Count consecutive occurrences
            while (i < chars.length &&
                   chars[i] == currentChar) {
                i++;
                groupLength++;
            }

            // Write the character
            chars[res++] = currentChar;

            // Write the group length if greater than 1
            if (groupLength > 1) {
                String count = String.valueOf(groupLength);

                for (char digit : count.toCharArray()) {
                    chars[res++] = digit;
                }
            }
        }

        return res;
    }
}

Dry Run

Consider the following input:

chars = ["c","c","b","a","a","a"]

The resulting array begins with:

["c","2","b","a","3", ...]

The returned length is 5.

Only the first res characters belong to the compressed result. Any remaining characters beyond this length can be ignored.

Complexity Analysis

Time Complexity: O(n)

Each character is processed a constant number of times. The outer loop processes groups, and the inner loop counts the characters in each group. Writing the frequency digits also takes linear time in total.

Space Complexity: O(1)

The algorithm modifies the original array and uses only a few variables. The frequency string requires at most a constant number of digits because the maximum group length is bounded by the size of the input array under typical integer-indexed array constraints.

Key Takeaways

• Use two pointers to read and write within the same array.

• Count consecutive repeating characters before overwriting their positions.

• Write frequency digits individually when the count is greater than one.

• Return the compressed length rather than the modified array.

• In-place algorithms help reduce additional memory usage.

Final Thoughts

String Compression is a useful problem for understanding the two-pointer technique and in-place array modification. The main idea is to separate the reading position from the writing position, allowing us to compress the input without allocating another result array.

Practice tracing the values of i, groupLength, and res to understand how the algorithm works for both single-character groups and groups with multiple digits in their frequency.