String Compression
(#443), Medium
Category: String, Two Pointer
Problem Statement
You're given an array of characters chars. Your task is to compress the array in-place using the following rules: - For each group of consecutive repeating characters: - If the count is 1, just write the character. - If the count is more than 1, write the character followed by the count (split digits like '12' into '1', '2'). The result must be written in-place and the function should return the new length of the array. 🚨 Space complexity must be O(1), i.e., constant extra space.
Examples
Input: chars = ['a','a','b','b','c','c','c']
Output: 6
Explanation: The array is compressed to ['a','2','b','2','c','3']
Input: chars = ['a']
Output: 1
Explanation: No compression needed, output remains ['a']
Input: chars = ['a','b','b','b','b','b','b','b','b','b','b','b','b']
Output: 4
Explanation: The array is compressed to ['a','b','1','2']
Approach
Two Pointer In-Place Compression
- Use a `read` pointer to scan the input array and a `write` pointer to overwrite the array with compressed values.
- Track the current character and count how many times it repeats consecutively.
- For each group, write the character once to the `write` pointer.
- If the count is more than 1, convert the count to a string and write each digit individually.
- Continue this process until the entire array is processed.
- Return the value of the `write` pointer as the new compressed length.
var compress = function (chars) {
let read = 0;
let write = 0;
while (read < chars.length) {
let count = 0;
let char = chars[read];
while (read < chars.length && chars[read] === char) {
read++;
count++;
}
chars[write++] = char;
if (count > 1) {
for (let c of count.toString()) {
chars[write++] = c;
}
}
}
return write;
};Complexity
Time: O(n)
Space: O(1)