Problem
Given an array of characters chars, compress it using the following rules. For each group of consecutive repeating characters, keep the character followed by its frequency if the frequency is greater than1. The compressed result must be stored in-place in the input array. Return the new length of the compressed array.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
chars = ["a","a","b","b","c","c","c"]Output
["a","2","b","2","c","3"]6Solution
This solution uses a Two Pointer approach. One pointer identifies the beginning of each group of consecutive characters, while another pointer scans the array to find the end of that group.For each group, we write the character to the current position and, if the group contains more than one character, write its count as well. A separate pointer keeps track of the position where the compressed result should be written.
Because the result is written directly into the input array, no additional array is required.
class Solution {
public int compress(char[] chars) {
int write = 0;
int i = 0;
while (i < chars.length) {
char current = chars[i];
int j = i;
while (j < chars.length && chars[j] == current) {
j++;
}
chars[write++] = current;
int count = j - i;
// Handle multi-digit frequencies (e.g., 12 -> '1', '2')
if (count > 1) {
String countStr = String.valueOf(count);
for (char c : countStr.toCharArray()) {
chars[write++] = c;
}
}
i = j;
}
return write;
}
}Complexity
Each character is processed while scanning the groups, and the compressed characters are written back into the array. Therefore, the time complexity isO(n). The compression is performed directly in the input array, so the algorithm uses
O(1) extra space, excluding the temporary representation of the count.
