String Compression
Compress an array of characters in place by replacing each run of a repeated letter with the letter and its count, using a read and a write pointer.
Problem Understanding
String Compression (LeetCode 443): given an array of characters chars, compress it in place. For each group of consecutive repeating characters, write the character, followed by the group's length if it is more than 1; lengths of 10 or more take several cells. Return the new length, using only O(1) extra space.
Examples: [a,a,b,b,c,c,c] → 6, [a,2,b,2,c,3]; [a] → 1; [a,b,b,b,b,b,b,b,b,b,b,b,b] → 4, [a,b,1,2].
The Intuition: Read Ahead, Write Behind
The compressed form is never longer than the input, so it can overwrite the array from the front.
- read scans to the end of the current run.
- write puts down the character and, if the run is longer than 1, the digits of its length.
- Repeat until read reaches the end.
It is the read/write pointer pair from Remove Duplicates from Sorted Array, writing a count where that lesson writes nothing.
Interactive Walkthrough
w = WRITE · r = READ
SCAN A RUN
chars (rewritten in place)
w
0
1
r
2
3
4
5
6
read
2
write
0
Run length
2
read scans a run of 'a' from 0 to 1: length 2
Next
Write 'a' at 0
chars
Green cells are the compressed output so far, the outlined cells are the run read just scanned, and the filled cell is the one just written. Try Example 3 to see a two-digit count.
Dry Run Table
Input: [a, a, b, b, c, c, c].
| Run | Length | Writes | write after |
|---|---|---|---|
| a at 0 to 1 | 2 | a, 2 | 2 |
| b at 2 to 3 | 2 | b, 2 | 4 |
| c at 4 to 6 | 3 | c, 3 | 6 |
Answer: 6; the array starts [a, 2, b, 2, c, 3].
The Solution Template
An outer loop per run, an inner loop to find its end, and the count written digit by digit.
String Compression Code
1var compress = function(chars) {2 let read = 0, write = 0;3 while (read < chars.length) {4 const ch = chars[read], start = read;5 while (read < chars.length && chars[read] === ch) read++;6 chars[write++] = ch;7 if (read - start > 1) {8 for (const digit of String(read - start)) {9 chars[write++] = digit;10 }11 }12 }13 return write;14};
Edge Cases & Common Mistakes
- Runs of length 1: write only the character, no "1".
- Counts of 10 or more: write each digit in its own cell.
- Returning the array: the answer is the new length, write.
- Building a new string: uses O(n) space; the problem asks for O(1) extra.
Summary
Scan each run with read, then write the character and, for runs longer than 1, the digits of the count. The output never outgrows the input, so it fits in place. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet