String Compression LeetCode 443 Guide

LeetCode 443 — String Compression gives you a character array chars and asks you to compress it in-place using run-length encoding, then return the new length. The compression rule is straightforward: each group of consecutive equal characters is encoded as the character followed by its count, but only if the count is greater than one.

For example, ["a","a","b","b","c","c","c"] compresses to ["a","2","b","2","c","3"] and returns 6. A single character like "a" appearing alone becomes just "a" — no count is appended. A group of 12 identical characters like "b" becomes "b","1","2" because 12 is written as its individual digits.

The constraint that makes this interesting is the in-place requirement with O(1) extra space. You cannot build a new array; you must overwrite the input array from the front. The return value is the new length of the compressed array, not the entire array content.

The key insight is using two pointers with distinct roles. The read pointer scans forward through the original array identifying runs of consecutive equal characters. The write pointer tracks where the next compressed character or digit should be placed in the array.

The write pointer always stays at or behind the read pointer, which guarantees you never overwrite characters you have not yet read. This is the critical invariant that makes in-place modification safe: by the time the write pointer reaches a position, the read pointer has already moved past it and extracted all the information needed.

The algorithm loops until the read pointer reaches the end of the array. For each iteration, it identifies the current character, counts how many consecutive times it appears, writes the character at the write position, then writes each digit of the count if the count exceeds one. Both pointers advance through the array in a single left-to-right pass, giving O(n) time complexity.

At the start of each iteration, the read pointer sits at the beginning of a new run. Record the current character as chars[read]. Then advance the read pointer forward as long as the next character equals the current character and the read pointer has not reached the end of the array.

When the inner while loop exits, the count of consecutive equal characters is read minus the starting position of the run (start). This gives you the run length without any extra data structure — just arithmetic on the two pointer values. For example if a run of "b" starts at index 3 and the read pointer ends at index 8, the count is 5.

The outer while loop condition is simply read < n where n is the total length of the array. Each iteration of the outer loop handles exactly one complete run, so the outer loop executes at most n times total across the entire algorithm. The inner loop work is also bounded by n across all iterations, giving the overall O(n) time guarantee.

After writing the character itself, check if the count is greater than one. If so, convert the count to its string representation and write each character of that string into the array at successive write positions. Count 1 writes nothing — the character alone represents a run of one. Count 2 writes "2". Count 12 writes "1" then "2".

In Python, converting the count to digits is simply str(count), and you can iterate over the string directly: for digit in str(count): chars[write] = digit; write += 1. In Java, use String.valueOf(count) to get the digit string, then iterate character by character writing each to chars[write++].

The write pointer advances once for each digit written. For single-digit counts (1-9) this is one step. For two-digit counts (10-99) this is two steps. The maximum count is n (all characters equal), which is at most 10^4 in the problem constraints — a five-digit number at most, so the write pointer advances at most 5 extra steps per run for count digits.

Trace ["a","b","b","b","b","b","b","b","b","b","b","b","b"] through the algorithm. The array has one "a" followed by twelve "b" characters. Both read and write start at index 0.

Iteration 1: start=0, c="a", read advances to 1 (next char is "b", not "a"). Count = 1-0 = 1. Write "a" at write=0, advance write to 1. Count is 1 so no digit is written.

Iteration 2: start=1, c="b", read advances through all twelve "b" characters to index 13. Count = 13-1 = 12. Write "b" at write=1, advance write to 2. Count 12 > 1: write "1" at write=2, write "2" at write=3, advance write to 4. The result is ["a","b","1","2",...] and the function returns write = 4.

Python solution: def compress(chars): read = write = 0; n = len(chars); while read < n: start = read; c = chars[read]; while read < n and chars[read] == c: read += 1; chars[write] = c; write += 1; count = read - start; if count > 1: for d in str(count): chars[write] = d; write += 1; return write. Two nested while loops, O(n) time, O(1) extra space.

Java solution: public int compress(char[] chars) { int read = 0, write = 0, n = chars.length; while (read < n) { char c = chars[read]; int start = read; while (read < n && chars[read] == c) read++; chars[write++] = c; int count = read - start; if (count > 1) { for (char d : String.valueOf(count).toCharArray()) chars[write++] = d; } } return write; }. The structure mirrors Python with the same two-pointer invariant.

Both solutions return the write pointer value as the new length. The time complexity is O(n) because each character is read once and written at most a constant number of times. The space complexity is O(1) because no extra arrays are allocated — only a handful of integer variables for the pointers and count.

String Compression belongs to the in-place array modification family — problems where you must transform an array without allocating extra space. Move Zeroes (LeetCode 283) uses the same two-pointer write-behind pattern to shift non-zero elements forward while keeping zeros at the back. Remove Duplicates from Sorted Array (LeetCode 26) applies the same read-ahead / write-behind structure to deduplicate a sorted array.

Reverse Words in a String (LeetCode 151) and Reverse Vowels of a String (LeetCode 345) both use two pointers but with an inward-converging pattern rather than the left-to-right scan used in compression. Understanding when to use convergent two pointers versus parallel left-to-right two pointers is a core skill for the string and array manipulation problem family.

The unifying theme across all these problems is the write pointer invariant: the write pointer always points to the next available slot, and it always lags behind or equals the read pointer. Once you internalize this invariant, in-place array modification problems become recognizable as variations on the same fundamental pattern, making them much faster to solve in an interview context.