String compression

XXX. String Compression

Two Pointer

String Manipulation

Problem Statement:

Given an array of characters chars, compress it using the following algorithm:

• For a group of consecutive repeating characters in the array, replace the group with the character followed by the group size.
• If the group size is 1, only include the character.

Return the new length of the array after compression. The array should be compressed in-place.

Algorithm:

The solution uses a two-pointer approach:

1. Initialize a pointer k to track the position in the array where the compressed characters are written.
2. Iterate through the array to identify consecutive groups of repeating characters:
• For each group, write the character at position k.
• If the group size is greater than 1, write the size of the group as individual digits.
3. Continue this process until all characters in the array have been processed.
4. Return k, which represents the new length of the array.

Complexity:

Time Complexity: O(n), where n is the length of the array. Each character is processed once.
Space Complexity: O(1), as the compression is performed in-place.

Java Implementation:

public class Solution {
    public int compress(char[] chars) {
        int k = 0; // Pointer to write compressed characters

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i]; // Current character

            // Identify the group of repeating characters
            int j = i;
            while (i < chars.length - 1 && chars[i + 1] == c) 
                i++;

            // Write the character to the compressed position
            chars[k++] = c;

            // If the group has more than one character, write the count
            if (i > j) {
                int len = i - j + 1; // Length of the group
                for (char digit : Integer.toString(len).toCharArray()) {
                    chars[k++] = digit;
                }
            }
        }

        return k; // New length of the compressed array
    }
}