String Compression (LC 443) — Read/Write Two Pointers

What does it solve?

Compress a char array in place: replace each run of a repeated character with the char followed by its count (counts > 1 only). "aaabbc" → "a3b2c", and return the new length. The counts' digits are written as separate characters.

Key insight: two pointers on the same array. A read pointer sweeps forward measuring each run's length; a write pointer lays down the character, then each digit of the count if it exceeds 1. Because the compressed form is never longer than the input, writing in place is always safe → O(N) time, O(1) space.

The core idea

read = 0, write = 0
while read < n:
  ch = s[read]; cnt = length of run
  s[write++] = ch
  if cnt > 1:
    for d in str(cnt): s[write++] = d
return write

Complexity

Time complexity

O(N)

The read pointer visits each character once; the write pointer never overtakes it. Digit-writing is bounded by the count length.

Space complexity

O(1)

Compression is done in place. The output length is at most the input length, so no reallocation.

Examples & edge cases

Live animation — read runs, write char + count in place

read pointer / run write pointer written output not yet written

Input array (read)

Same array being overwritten (write)

Press Play to begin…

Current step detail

read = — write = — run = — length = —

Step — of —

read pointer

—

scanning

write pointer

—

next slot

run length

—

current char

output length

—

chars written

Select an example and press Play to start.

✓ Done

SpeedMedium

Step-by-step table

Step	phase	read	write	char	count	output

C++ implementation

string_compression.cpp

#include <bits/stdc++.h>
using namespace std;

// Compress chars in place; return the new length (LeetCode 443)
int compress(vector<char>& s) {
    int n = s.size(), read = 0, write = 0;
    while (read < n) {
        char ch = s[read];
        int cnt = 0;
        while (read < n && s[read] == ch) { read++; cnt++; } // measure the run

        s[write++] = ch;                     // always write the char
        if (cnt > 1) {                       // counts of 1 are omitted
            for (char d : to_string(cnt))     // write each digit
                s[write++] = d;
        }
    }
    return write;
}

int main() {
    vector<char> s = {'a','a','a','b','b','c'};
    int len = compress(s);
    for (int i = 0; i < len; i++) cout << s[i]; // a3b2c
    cout << " (len " << len << ")\n";
    return 0;
}

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem