{ }SolveLogs
⌕
Home / Two Pointers / #443
LeetCode #443 Medium

String Compression

String Compression is LeetCode 443 (Medium). You get an array of characters chars. Compress it in place: for each run of equal characters in a row, write the character, then the run's length if it is more than 1.

  • A count of 10 or more is split into one cell per digit, so 12 takes two cells, '1' and '2'.
  • Return the new length. The judge ignores every cell after it.
  • Only constant extra space is allowed, so the result must be written into chars itself.
Constraints
  • 1 <= chars.length <= 2000
  • chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.
stringtwo-pointers
Open on LeetCode ↗
02

Intuition

Read each run, then write its short form over the front of the same array. This is safe because the short form of a run is never longer than the run itself:

  • Run of 1: writes 1 cell, the character.
  • Run of 2 to 9: writes 2 cells, the character and one digit.
  • Run of 10 or more: writes 1 cell plus one per digit, far fewer than the run.

So the write pointer can never overtake the read pointer. Every write lands on a cell that has already been read, and no character still waiting to be read is lost.

How to spot this pattern

Rewriting an array into itself with two pointers, a slow write and a fast read, is the same pattern as Remove Duplicates from Sorted Array and Move Zeroes. The real work is always showing that write stays behind read.

03

Approach

Try it first

Before reading on, work out how many cells a run of 1, a run of 5 and a run of 12 should take. Then check whether writing over the array while you are still reading it can ever destroy a character you have not read. Aim for O(n) time and O(1) space.

1

Start both pointers at 0

read scans the original characters and write marks the next cell of the compressed result. Both point into the same array, which is how the solution stays within constant extra space.

2

Measure one run

Remember ch = chars[read], then move read forward while chars[read] == ch, counting the steps in run. The scan stops at the first different character or at the end of the array, so the last run needs no extra code.

3

Write the character

Put ch into chars[write] and move write on by one. Every run writes its character, and a run of 1 writes nothing else. By now read has moved past the whole run, so this cell is free to overwrite.

4

Write the count digit by digit

If run > 1, turn it into text with str(run) and write each digit into its own cell, left to right. Going through the string keeps the digits in reading order with no arithmetic.

5

Return the write position

When read reaches the end, write equals the number of cells the compressed result fills. That is exactly the length the judge expects, and it reads that many cells from the front.

04

String Compression solution in Python | C++ | Java

▶1class Solution:
▶2 def compress(self, chars: List[str]) -> int:
▶3 n = len(chars)
▶4 write = read = 0
▶5 while read < n:
▶6 ch = chars[read]
▶7 run = 0
▶8 while read < n and chars[read] == ch:
▶9 read += 1
▶10 run += 1
▶11 chars[write] = ch
▶12 write += 1
▶13 if run > 1:
▶14 for d in str(run):
▶15 chars[write] = d
▶16 write += 1
▶17 return write
charsa0a1b2b3c4c5c6readwritecurrent runnone yetread and write both start at cell 0
read0
write0
n7
read walks over the original characters; write marks where the next compressed character goes. Both share the same array, so no extra space is used.
charsa0a1b2b3c4c5c6readwritecurrent runa×0copiesnew run starts with 'a'
ch'a'
read0
write0
Cell 0 holds 'a', the first character of a new run. Its length is not known yet, so read scans forward and counts.
charsa0a1b2b3c4c5c6readwritecurrent runa×1copy1st 'a' → keep reading
run1
read1
Cell 0 is the run's first 'a', so the count is 1. Cell 1 also holds 'a', so read keeps going.
charsa0a1b2b3c4c5c6readwritecurrent runa×2copies2nd 'a' → next is 'b', run ends
run2
read2
Cell 2 holds 'b', not 'a', so this run is 2 long and the scan stops.
charsa0a1b2b3c4c5c6readwritecurrent runa×2copieswrite 'a' into cell 0
chars[0]'a'
write1
read2
Write the run's character at cell 0. Its count follows next. write is at 1 and read is at 2, so nothing unread has been overwritten.
charsa021b2b3c4c5c6readwritecurrent runa×2copiescount 2 → cell 1
chars[1]'2'
write2
read2
The count 2 is one digit, so it fills one cell. The run used 2 cells and now takes 2, which is why write never passes read.
charsa021b2b3c4c5c6readwritecurrent runb×0copiesnew run starts with 'b'
ch'b'
read2
write2
Cell 2 holds 'b', the first character of a new run. Its length is not known yet, so read scans forward and counts.
charsa021b2b3c4c5c6readwritecurrent runb×1copy1st 'b' → keep reading
run1
read3
Cell 2 is the run's first 'b', so the count is 1. Cell 3 also holds 'b', so read keeps going.
charsa021b2b3c4c5c6readwritecurrent runb×2copies2nd 'b' → next is 'c', run ends
run2
read4
Cell 4 holds 'c', not 'b', so this run is 2 long and the scan stops.
charsa021b2b3c4c5c6readwritecurrent runb×2copieswrite 'b' into cell 2
chars[2]'b'
write3
read4
Write the run's character at cell 2. Its count follows next. write is at 3 and read is at 4, so nothing unread has been overwritten.
charsa021b223c4c5c6readwritecurrent runb×2copiescount 2 → cell 3
chars[3]'2'
write4
read4
The count 2 is one digit, so it fills one cell. The run used 2 cells and now takes 2, which is why write never passes read.
charsa021b223c4c5c6readwritecurrent runc×0copiesnew run starts with 'c'
ch'c'
read4
write4
Cell 4 holds 'c', the first character of a new run. Its length is not known yet, so read scans forward and counts.
charsa021b223c4c5c6readwritecurrent runc×1copy1st 'c' → keep reading
run1
read5
Cell 4 is the run's first 'c', so the count is 1. Cell 5 also holds 'c', so read keeps going.
charsa021b223c4c5c6readwritecurrent runc×2copies2nd 'c' → keep reading
run2
read6
Cell 5 is 'c' again, so the run grows to 2. Cell 6 also holds 'c', so read keeps going.
charsa021b223c4c5c6writecurrent runc×3copies3rd 'c' → end of array, run ends
run3
read7
read has passed the last cell, so the final run is 3 long. The same loop that handles every other run writes it too.
charsa021b223c4c5c6writecurrent runc×3copieswrite 'c' into cell 4
chars[4]'c'
write5
read7
Write the run's character at cell 4. Its count follows next. write is at 5 and read is at 7, so nothing unread has been overwritten.
charsa021b223c435c6writecurrent runc×3copiescount 3 → cell 5
chars[5]'3'
write6
read7
The count 3 is one digit, so it fills one cell. The run used 3 cells and now takes 2, which is why write never passes read.
charsa021b223c435c6writecurrent runall readanswer: 6, the first 6 cells
return6
chars"a2b2c3"first 6 cells
Return 6. The judge reads only the first 6 cells, a2b2c3; the grey cells after them are leftovers and can hold anything.
05

Common pitfalls

Putting the whole count in one cell

✗ Wrong
chars[write] = str(run)
write += 1
✓ Right
for d in str(run):
    chars[write] = d
    write += 1

On ["a"] + ["b"] * 12 this stores "12" in a single cell and returns 3. The answer is 4, with '1' and '2' in separate cells.

Writing a count for a run of 1

✗ Wrong
chars[write] = ch
write += 1
for d in str(run): ...
✓ Right
if run > 1:
    for d in str(run): ...

On ["a","b","c"] the '1' after 'a' lands on cell 1 before 'b' has been read, so the input is destroyed. The correct result is the array unchanged, with length 3.

Peeling digits off with % 10

✗ Wrong
while run:
    chars[write] = str(run % 10)
    run //= 10
    write += 1
✓ Right
for d in str(run):
    chars[write] = d
    write += 1

% 10 gives the last digit first, so twelve 'b's become b, 2, 1. Either reverse those cells afterwards or write the digits from the number's string.

06

Edge cases

No character repeats, like ["a","b","c"]

Every run is 1 long, so each character is written back onto its own cell and the answer is the original length.

The characters are digits, like ["2","2","2"]

The result is '2', '3'. It looks odd to a person, but the judge compares cells, so the code needs nothing special.

07

Complexity

Time
O(n)
Space
O(1)
Each cell is passed once by read and written at most once by write. A run is at most 2,000 long, so str(run) has at most 4 characters, which counts as constant space.
08

String Compression FAQ

Is this the same as run-length encoding?

It is run-length encoding with two changes: a run of 1 keeps no count, and the result must overwrite the input instead of being built as a new string. A plain encoder that returns "a1b1" or allocates a new string breaks both rules.

How is String Compression II different?

LeetCode 1531 lets you delete up to k characters first and asks for the shortest encoded length you can reach. That is a dynamic-programming problem over positions and deletions, so the single two-pointer pass here does not apply.

← Prev · #442
Find All Duplicates in an Array
Next · #448 →
Find All Numbers Disappeared in an Array