String Compression
String Compression: compress the character array in place by replacing each run of repeats with the character followed by its count, and return the new length. Runs of length 1 keep no count.
- 1 <= chars.length <= 2000
- chars[i] is a lowercase English letter, uppercase English letter, or digit.
Intuition
Two pointers with different jobs: a read pointer that scans runs, and a write pointer that lays down the compressed output behind it. The write pointer can never overtake the read pointer, because a run of length L produces at most 1 + digits(L) characters, which never exceeds L. That is why in-place is safe.
Read and write pointers moving at different speeds is the in-place-rewrite pattern — the same as Remove Duplicates from Sorted Array and Move Zeroes. The reusable insight is proving the write pointer lags the read pointer, which is what licenses mutating the array you are still scanning.
Approach
Before reading on: convince yourself the write pointer can never pass the read pointer. Then work out what a run of twelve identical characters should actually place in the array. Aim for O(n) with O(1) space.
Separate reading from writing
Keep read for scanning and write for output. At each run, note the character, advance read while the same character repeats, and compute the run length. Then write the character at write, and if the length exceeds 1, write its digits too. Because compression never expands, write stays at or behind read and the not-yet-read tail is never clobbered — this is the invariant that makes the whole thing legal in place.
Multi-digit counts must be written digit by digit
A run of 12 becomes the characters '1' and '2', not a single element holding 12. Convert the number to its string form and write each digit separately. Forgetting this is the classic bug: it passes on runs under 10 and breaks on longer ones, which small hand-tested examples never expose.
Return length, not string
The problem asks for the new length; the caller reads only the first write entries. Anything beyond that is ignored, so there is no need to truncate or clear the tail. Time is O(n) — each element is read once and written at most once — with O(1) extra space, which is the entire point of the exercise.
Solution & live demo
Common pitfalls
Writing a multi-digit count as one element
chars[write] = str(length)
for digit in str(length):
chars[write] = digit
write += 1A count of 12 must occupy two array slots, '1' and '2'. Storing "12" in a single slot passes tests with short runs and fails the moment a run reaches ten.
Writing a count of 1
chars[write] = char write += 1 for digit in str(length): ...
if length > 1:
for digit in str(length): ...The specification says a single character is left alone. Writing 'a1' both lengthens the output and produces the wrong answer.
Returning the array instead of the length
return chars
return write
The problem's contract is to mutate in place and return how many entries are meaningful. The judge reads the first write characters; returning the array fails the signature.
Edge cases
Every run has length 1, so no counts are written and the length is unchanged at 3.
Writes 'a' then '2', giving length 2 — the same length, still correct.
Writes 'a','1','2' — the count is split into separate digit characters.
One run of length 1; the answer is 1 with no count written.
The inner while stops at the array bound, so the final run is written like any other.