String Compression

Problem#

Given an array of characters, compress it in place: each run becomes the character followed by its run length (omit the length if it’s 1). Return the new length.

Examples#

["a","a","b","b","c","c","c"] → 6 with prefix ["a","2","b","2","c","3"]
["a"] → 1, ["a"]
["a","b","b","b","b","b","b","b","b","b","b","b","b"] → 4 with ["a","b","1","2"]

Constraints#

1 <= chars.length <= 2000.

Hints#

Hint 1

Write the character at the run start, then count, then emit each digit.

Approach#

Three indices: read i, write w, run-start j. Walk forward; at the end of each run (i == end-of-run), write the character at w, then if count > 1, write each decimal digit. Multi-digit counts are written most-significant-first via a small reverse trick (or by computing digits then reversing the just-written range).

Solution#

class Solution {
public:
    int compress(vector<char>& chars) {
        int w = 0, i = 0, n = chars.size();
        while (i < n) {
            int j = i;
            while (j < n && chars[j] == chars[i]) ++j;
            chars[w++] = chars[i];
            int count = j - i;
            if (count > 1) {
                int start = w;
                while (count > 0) {
                    chars[w++] = '0' + (count % 10);
                    count /= 10;
                }
                reverse(chars.begin() + start, chars.begin() + w);
            }
            i = j;
        }
        return w;
    }
};

func compress(chars []byte) int {
    w, i, n := 0, 0, len(chars)
    for i < n {
        j := i
        for j < n && chars[j] == chars[i] {
            j++
        }
        chars[w] = chars[i]
        w++
        count := j - i
        if count > 1 {
            start := w
            for count > 0 {
                chars[w] = byte('0' + count%10)
                w++
                count /= 10
            }
            for l, r := start, w-1; l < r; l, r = l+1, r-1 {
                chars[l], chars[r] = chars[r], chars[l]
            }
        }
        i = j
    }
    return w
}

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        w, i, n = 0, 0, len(chars)
        while i < n:
            j = i
            while j < n and chars[j] == chars[i]:
                j += 1
            chars[w] = chars[i]
            w += 1
            count = j - i
            if count > 1:
                start = w
                while count > 0:
                    chars[w] = str(count % 10)
                    w += 1
                    count //= 10
                # reverse the digits we just wrote
                l, r = start, w - 1
                while l < r:
                    chars[l], chars[r] = chars[r], chars[l]
                    l += 1
                    r -= 1
            i = j
        return w

function compress(chars) {
    let w = 0, i = 0;
    const n = chars.length;
    while (i < n) {
        let j = i;
        while (j < n && chars[j] === chars[i]) j++;
        chars[w++] = chars[i];
        let count = j - i;
        if (count > 1) {
            const start = w;
            while (count > 0) {
                chars[w++] = String(count % 10);
                count = Math.floor(count / 10);
            }
            // reverse the digits we just wrote
            let l = start, r = w - 1;
            while (l < r) {
                [chars[l], chars[r]] = [chars[r], chars[l]];
                l++;
                r--;
            }
        }
        i = j;
    }
    return w;
}

class Solution {
    public int compress(char[] chars) {
        int w = 0, i = 0, n = chars.length;
        while (i < n) {
            int j = i;
            while (j < n && chars[j] == chars[i]) j++;
            chars[w++] = chars[i];
            int count = j - i;
            if (count > 1) {
                int start = w;
                while (count > 0) {
                    chars[w++] = (char) ('0' + count % 10);
                    count /= 10;
                }
                // reverse digits
                int l = start, r = w - 1;
                while (l < r) {
                    char tmp = chars[l];
                    chars[l] = chars[r];
                    chars[r] = tmp;
                    l++;
                    r--;
                }
            }
            i = j;
        }
        return w;
    }
}

function compress(chars: string[]): number {
    let w = 0, i = 0;
    const n = chars.length;
    while (i < n) {
        let j = i;
        while (j < n && chars[j] === chars[i]) j++;
        chars[w++] = chars[i];
        let count = j - i;
        if (count > 1) {
            const start = w;
            while (count > 0) {
                chars[w++] = String(count % 10);
                count = Math.floor(count / 10);
            }
            // reverse the digits we just wrote
            let l = start, r = w - 1;
            while (l < r) {
                [chars[l], chars[r]] = [chars[r], chars[l]];
                l++;
                r--;
            }
        }
        i = j;
    }
    return w;
}

Editorial#

In-place compression works because the compressed form is never longer than the source (the worst case n=1 writes 1 char; any run length ≥ 2 writes at most 1 + ceil(log10(count)) chars, bounded by 1 + len of run). The reverse handles multi-digit counts cleanly without a temporary buffer.

Complexity#

Time: O(n).
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#