String Compression
On this page
Problem statement
Compress an array of characters in place. Replace every run of the same character with the character followed by the run's length, but only write the length when the run is longer than 1. A length of 10 or more takes one array cell per digit. Return the new length; only the first that many cells are checked. Use O(1) extra space.
A short question that checks careful in-place array work: two pointers moving at different speeds over the same array. It is the run-length encoding behind many simple file formats. Original problem: LeetCode 443.
Example

Input: ["a","a","a","b","b","c"]
Output: 5, array starts with ["a","3","b","2","c"]
Input: twelve "z" characters
Output: 3, array starts with ["z","1","2"]
Input: ["x"]
Output: 1, array starts with ["x"] # a run of 1 gets no count
Constraints (assumed)
- 1 ≤ length ≤ 2,000; the array holds letters, digits or symbols.
- Must use O(1) extra space (a few variables, no new array).
What this question tests
- Using a read pointer and a write pointer on the same array, and knowing why the writer never overtakes the reader.
- Grouping runs cleanly, including the last one.
- Small details: counts with several digits, and no count for runs of length 1.
Questions to ask first
- Is a count written for runs of length 1? (Here: no.)
- How are counts of 10 or more written? (Here: one cell per digit.)
- Can digits appear in the input? (Here: yes, but that doesn't change the algorithm; it just makes the output ambiguous to decode.)
- Must it be in place? (Here: yes, O(1) extra space.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.