String Compression

mediumAmazon-tagged: Arrays & Strings45 stepsJava · Python · C++

Compress runs of repeated characters in place: "aabccc" becomes "a2bc3". A read pointer finds each run; a write pointer writes the character and, if the run is longer than 1, each digit of its length. Return the new length.

▶ Watch the animated trace

Traced input: chars = [a, a, b, b, c, c, c] → 6, ["a", "2", "b", "2", "c", "3"]. Original problem: neetcode.io/problems/string-compression

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

The write pointer never passes the read pointer.

Key idea

Find the end of the current run with the read pointer.
Write the character, then the count's digits if the count > 1.
Counts ≥ 10 take several characters: write String.valueOf(count) digit by digit.

Common mistakes

Writing "a1" for single characters.
Writing the count as one char, which breaks for counts ≥ 10.

Solution

Java

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++;
        int count = read - start;
        chars[write++] = c;
        if (count > 1) {
            for (char d : String.valueOf(count).toCharArray()) chars[write++] = d;
        }
    }
    return write;
}

Python

def compress(chars: List[str]) -> int:
    write = read = 0
    while read < len(chars):
        c, start = chars[read], read
        while read < len(chars) and chars[read] == c: read += 1
        chars[write] = c
        write += 1
        if read - start > 1:
            for d in str(read - start):
                chars[write] = d
                write += 1
    return write

C++

int compress(vector<char>& chars) {
    int write = 0, read = 0, n = chars.size();
    while (read < n) {
        char c = chars[read];
        int start = read;
        while (read < n && chars[read] == c) read++;
        int count = read - start;
        chars[write++] = c;
        if (count > 1) {
            for (char d : to_string(count)) chars[write++] = d;
        }
    }
    return write;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single character No count is written for a run of 1.	`chars = [a]`	`1, ["a"]`
Run of 12 12 is written as two digits.	`chars = [a, b × 12]`	`4, ["a", "b", "1", "2"]`
No repeats Unchanged.	`chars = [a, b, c]`	`3, ["a", "b", "c"]`