String Compression(#443)
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
Input: chars = ['a']
Output: 1
Input: chars = ['a','b','b','b','b','b','b','b','b','b','b','b','b']
Output: 4
🧠 Approach
We solve this using the Two Pointer technique:
• **Read Pointer:** Scans through the array to find groups of repeating characters.
• **Write Pointer:** Writes the compressed version back into the array.
For each group of repeating characters:
- We write the character to the `write` pointer.
- If the character repeats more than once, convert the count to a string and write each digit separately.
This is done **in-place** without using extra space. We return the new length of the compressed array (i.e., the final position of the `write` pointer).
💻 Code
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;
};
console.log(compress(['a','a','b','b','c','c','c'])); // 6📈 Complexity
Time: O(n) – each character is read and written once
Space: O(1) – in-place modification using constant space