String compression

Run-length encode in place: count each run of identical characters, then write the character followed by its count.

Time O(n)Space O(1)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

read scans forward through one run of identical characters at a time while write places the compressed result. A run of length 1 is written as just the character; a longer run is written as the character followed by its count as digits.

Code

public static int Compress(char[] chars) {
    int read = 0, write = 0;
    while (read < chars.Length) {
        char c = chars[read];
        int start = read;
        while (read < chars.Length && chars[read] == c) read++;
        chars[write++] = c;
        int count = read - start;
        if (count > 1)
            foreach (char d in count.ToString())
                chars[write++] = d;
    }
    return write;
}

Tips

Writing happens at the write pointer, which only moves forward, so the compression works in place without extra space.
A run can have a count of 10 or more, which is why the count is written one digit at a time.

In the .NET library

This differs from the longest-run counting seen elsewhere: here every run is written out, not just tracked for a maximum.