String Compression

medium string two pointers

Problem

Given an array of characters chars, compress it using the following algorithm: Begin with an empty string s. For each group of consecutive repeating characters in chars: If the group's length is 1, append the character to s. Otherwise, append the character followed by the group's length.

Inputchars = ['a','a','a','b','b','c']

Output5 (chars becomes ['a','3','b','2','c', …])

Runs: a×3, b×2, c×1 → "a3b2c".

chars (typed as a string)

def compress(chars):
    write = read = 0
    while read < len(chars):
        run = read
        while run < len(chars) and chars[run] == chars[read]:
            run += 1
        chars[write] = chars[read]; write += 1
        n = run - read
        if n > 1:
            for d in str(n):
                chars[write] = d; write += 1
        read = run
    return write

function compress(chars) {
  let write = 0, read = 0;
  while (read < chars.length) {
    let run = read;
    while (run < chars.length && chars[run] === chars[read]) run++;
    chars[write++] = chars[read];
    const len = run - read;
    if (len > 1) for (const d of String(len)) chars[write++] = d;
    read = run;
  }
  return write;
}

class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 0;
        while (read < chars.length) {
            int run = read;
            while (run < chars.length && chars[run] == chars[read]) run++;
            chars[write++] = chars[read];
            int len = run - read;
            if (len > 1) for (char d : String.valueOf(len).toCharArray()) chars[write++] = d;
            read = run;
        }
        return write;
    }
}

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

Explanation

We compress runs of the same character in place using two pointers: read scans through the input, and write marks where the next compressed character goes. Because the compressed form is never longer, write always stays behind read.

For each run we start at read and advance a helper run while the character keeps repeating. The run length is n = run - read. We write the character once at chars[write], and if n > 1 we also write each digit of that count (handling lengths like 12 by writing '1' then '2').

After handling a run, we jump read to run to start the next group. The function finally returns write, the new compressed length, with the answer stored at the front of the same array.

Example: chars = ['a','a','a','b','b','c']. The runs are a×3, b×2, c×1. We write a 3 b 2 c, producing "a3b2c" of length 5, so the return value is 5 (the lone c gets no count).

Each character is read once and written at most once, so this runs in a single linear pass with no extra array.

Time: O(n) Space: O(1) in place