String Compression
Problem statement
You're given an array of characters. Whenever the same character repeats several times in a row, replace that whole run with just the character followed by how many times it repeated — a single occurrence is left as just the character, with no count written after it. Write this compressed result back into the same array, overwriting the original characters, and return how many characters the compressed result takes up. Anything left over past that length in the array doesn't matter.
The catch is the counting itself: if a run is 10 or longer, its count is written out as multiple digit characters ("12" becomes the two characters '1' and '2'), just like you'd expect from writing the number normally.
This is the same idea as run-length encoding a series of repeated readings — for example collapsing "OK OK OK OK OK FAIL FAIL OK" health-check results down to "OK5 FAIL2 OK1" before shipping it somewhere with limited bandwidth, or compacting a long run of identical status codes in a log summary.
Examples
Example 1
Input: chars = ["a","a","b","b","c","c","c"]
Output: 6, chars = ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". Each group of 2 or more becomes the character followed by its count, giving "a2b2c3" — six characters in total.
Example 2
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: 4, chars = ["a","b","1","2"]
Explanation: The groups are "a" (length 1, left alone) and "bbbbbbbbbbbb" (length 12, a run of 12 b's). Since 12 has two digits, it's written as the two separate characters '1' and '2', giving "ab12" — four characters in total.
Hints
Approach
Optimal: In-place two pointers
Intuition
The brute-force version's only real problem is that it writes to a new place before it knows the final answer belongs in the original array. But look at the relationship between reading and writing: the write position can never get ahead of the read position, because writing a compressed group (1–5 characters) always takes at most as many characters as reading that group took (which was at least as many, since the group has at least 1 repeat). That means it's always safe to write the compressed output directly into the same array we're still reading from — the write pointer trails behind or matches the read pointer, never passes it.
So instead of building a separate list, keep two indices: read, which scans forward finding runs the same way as before, and write, which places each run's compressed form directly back into chars. Because write never overtakes read, we never destroy data we haven't looked at yet.
Steps
- Start both
readandwriteat index 0. - At each step, note the character at
readand count how many times it repeats consecutively, advancingreadpast the whole run. - Write that character into
chars[write]and advancewrite. - If the run's count was more than 1, write each digit of the count (converted to its characters) into the next positions, advancing
writeonce per digit. - Repeat until
readreaches the end of the array, then returnwriteas the new length.
Dry run
chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
| read scans | count | chars[write..] written | write after |
|---|---|---|---|
| "a" | 1 | 'a' | 1 |
| "bbbbbbbbbbbb" | 12 | 'b', '1', '2' | 4 |
Final array (first 4 slots): ['a','b','1','2'] — matching example 2 exactly.
Edge cases: a single-character array writes just that one character and write ends at 1, so no count is ever appended for a group of size 1. Because write always trails read, overwriting a character at chars[write] is always safe — that position has either already been fully read, or is being read again as part of the current run being counted (which happens before the write for that run occurs).
Complexity
Time O(n) - Every character is looked at exactly once by the reading pointer as it scans through runs, and every character written (the run's letter plus at most a few digit characters) is written exactly once by the writing pointer. Both pointers only ever move forward, so the total work is linear in the length of the array.
Space O(1) - No separate list or string is used at all; the array is read and written in place with just a few index and counter variables. Converting a run's count to its digit characters uses a small, fixed amount of extra room (at most 4 digits, since counts are at most 2000), which doesn't grow with the input and is treated as constant space here.
class Solution:
def compress(self, chars: list[str]) -> int:
n = len(chars)
read = 0
write = 0
while read < n:
ch = chars[read]
count = 0
while read < n and chars[read] == ch:
read += 1
count += 1
chars[write] = ch
write += 1
if count > 1:
for digit in str(count):
chars[write] = digit
write += 1
return write
if __name__ == "__main__":
chars1 = ["a", "a", "b", "b", "c", "c", "c"]
n1 = Solution().compress(chars1)
print(n1, chars1[:n1]) # 6 ['a', '2', 'b', '2', 'c', '3']
chars2 = ["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"]
n2 = Solution().compress(chars2)
print(n2, chars2[:n2]) # 4 ['a', 'b', '1', '2']RecapThe whole problem in a few lines, for the night before
- Spot it: compress runs of a character in place, like aaabb into a3b2
- Idea: two pointers: a read pointer finds the length of each run, a write pointer writes the character and then the count digits
- Cost: O(n) time, O(1) extra space
- Trap: do not write a count of 1, and write counts of 10 or more as separate digit characters
Interview follow-ups
What if a run's count needs to be written as a fixed 2-digit field (e.g. always "05" instead of "5")?
Compute the count as before, but when writing its digits, pad it with a leading
'0'first if it's a single digit. This only changes the small block of code that writes the digits — the two-pointer scanning stays the same. The in-place safety argument still holds for any run of length 2 or more: reading a run of lengthk >= 2consumes at least 2 characters, and writing it now takes at most 3 (the letter plus a 2-digit count), so fork >= 3the write is still no longer than the read. The one case to check by hand is a run of exactly length 2 (like "aa"), which reads 2 characters but would now write 3 ('a', '0', '2') — one character more than it read. If padded counts are required, you'd need to fall back to a small fixed lookahead buffer (holding just the next couple of unread characters) rather than writing fully in place for runs that short.What if
charsis actually a huge memory-mapped file on disk instead of an in-memory array?The same two-pointer approach still works, since it makes one forward pass and never seeks backward past where it has already written — that's exactly the access pattern memory-mapped or streamed file I/O prefers. The main change is that
readandwritebecome file offsets rather than array indices, and each single-character access becomes a small buffered read or write instead of an array lookup, so you'd add a small in-memory buffer to avoid a syscall per character.
Frequently asked questions
The brute-force and optimal approaches follow the exact same scanning logic — find each run, emit the character and its count — they differ only in where the output is written. There isn't a meaningfully different algorithm in between; the whole problem is really about noticing that the same single-pass logic can safely target the input array itself instead of a new one, which is a one-step jump rather than a ladder of techniques.
Because a run of length k (k >= 1) is read as k characters but written as at most 1 + (number of digits in k) characters, and for every possible run length that written amount is never more than k. So write is always at or behind read by the time we write anything for the current group, meaning we're only ever overwriting positions that have already been fully consumed.
Run-length encoding is a real, lightweight compression technique for data with long repeated runs — repeated health-check results, a flat metric that hasn't changed in a while, or a status column in a report where the same value appears many rows in a row. Being asked to do it in constant extra space also tests whether you can reason carefully about in-place array mutation without corrupting data you haven't read yet.