The String Compression coding problem involves taking an array of characters and compressing it in-place using a basic run-length encoding scheme. For a group of consecutive repeating characters, you replace them with the character followed by the number of repetitions (but only if the count is greater than 1). The goal is to modify the original array and return the new length of the compressed string. Space complexity is a major constraint, as the operation must be done in-place.
This is one of the most frequently asked String Compression interview questions, appearing in interviews for almost every major tech company including Apple, Uber, and Amazon. It is a fundamental test of "Two Pointers" logic and array manipulation. It evaluates a candidate's ability to manage multiple indices simultaneously—one for reading the original characters and another for writing the compressed results—without losing data or using extra space.
This problem is a classic example of the Two Pointers, String interview pattern. One pointer (the "read" pointer) iterates through the array to identify groups of identical characters. Another pointer (the "write" pointer) tracks where the next compressed character and its count should be placed. A third pointer or a nested loop is often used to find the end of the current group of characters. When a group is identified, the character is written, and if the count > 1, the digits of the count are written sequentially.
Input: ["a", "a", "b", "b", "b", "c"]
["a", "2", ...]["a", "2", "b", "3", ...]["a", "2", "b", "3", "c"]. Return length 5.A very common mistake is not handling counts that are 10 or greater. For example, if there are 12 'a's, you must write 'a', then '1', then '2' as separate character elements. Another mistake is forgetting to handle the final group of characters after the loop ends. Some candidates also struggle with the in-place requirement and accidentally overwrite characters they haven't read yet, although with the compression logic, the write pointer will never overtake the read pointer.
Practice in-place array modifications until you are comfortable with the "Read/Write Pointer" pattern. It's a very common requirement in technical interviews. When dealing with numbers that need to be converted to strings (like the counts), remember that you can get the digits by converting the number to a string or by using a loop with % 10 and reverse. Always test your code with edge cases like an empty array, an array with all unique characters, or an array with one character repeating many times.