String Compression

Free with account Updated Nov 19, 2026 · 5 min read
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

    aaabbc becomes a3b2c in the first five cells; the last cell is left over and ignored.
    aaabbc becomes a3b2c in the first five cells; the last cell is left over and ignored.
    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

    1. Is a count written for runs of length 1? (Here: no.)
    2. How are counts of 10 or more written? (Here: one cell per digit.)
    3. Can digits appear in the input? (Here: yes, but that doesn't change the algorithm; it just makes the output ambiguous to decode.)
    4. Must it be in place? (Here: yes, O(1) extra space.)