String Compression
Medium Read/write pointers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Compress a char array in place: each run of a repeated character becomes the character followed by the run length (only if the length is more than 1). Return the new length.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: in place, write each letter followed by its run length (if more than 1).
Why this works: read a whole run, write the letter and the digits of the count; the write pointer never passes the read pointer.
Example: [a, a, b, b, c, c, c]
a×2 → "a2", b×2 → "b2", c×3 → "c3"[a, 2, b, 2, c, 3] → length 6
✦Hints open one at a time
↗Approach
For each run, write the character, then, if the run is longer than 1, write the digits of its length. The write pointer never passes the read pointer, so it's safe in place.
</>Solution (Java)
class Solution {
public int compress(char[] chars) {
int write = 0, read = 0;
while (read < chars.length) {
char c = chars[read];
int start = read;
while (read < chars.length && chars[read] == c) read++;
chars[write++] = c;
int len = read - start;
if (len > 1) {
for (char d : String.valueOf(len).toCharArray()) chars[write++] = d; // every digit
}
}
return write;
}
}!Common mistake
Writing the count as a single char (char) count, which breaks for runs of 10+.
- Time: O(n).
- Space: O(1).