LeetCode 443 String Compression - Two Pointers (Med, Java, O(n))

Anni HuangAnni Huang
3 min read

Algorithm Overview

The solution implements an in-place string compression algorithm using a two-pointer approach. Here's how it works:

  • read: scans through the original characters
  • write: tracks where to place the compressed output

Step-by-Step Breakdown

1. Initialize Pointers

int write = 0, read = 0;

Both pointers start at the beginning of the array.

2. Main Loop Structure

while (read < n) {
    char currentChar = chars[read];
    int count = 0;
    // ...
}

Continue until we've processed all characters.

3. Count Consecutive Characters

while (read < chars.length && chars[read] == currentChar) {
    count++;
    read++;
}

This inner loop counts how many times the current character repeats consecutively. The read pointer advances through all identical characters.

4. Write the Character

chars[write++] = currentChar;

Always write the character itself first, then increment the write pointer.

5. Write the Count (if > 1)

if (count > 1) {
    String countStr = String.valueOf(count);
    for (char c : countStr.toCharArray()) {
        chars[write++] = c;
    }
}

If the character appears more than once, convert the count to a string and write each digit individually.

Problem Solution

class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 0;
        int n = chars.length;
        while (read < n){
            char currentChar = chars[read];
            int count = 0;
            // count how many times currentChar repeats
            while (read<chars.length && chars[read] == currentChar) {
                count++;
                read++;
            }
            // write the character
            chars[write++] = currentChar;

            // if count>1, write its digits
            if (count>1) {
                String countStr = String.valueOf(count);
                for (char c: countStr.toCharArray()){
                    chars[write++] = c;
                }
            }
        }
        return write;
    }
}

Example Walkthrough

For input ['a','a','b','b','c','c','c']:

  1. First iteration: currentChar = 'a', count = 2

    • Write 'a' at position 0
    • Write '2' at position 1
    • Result so far: ['a','2',...]
  2. Second iteration: currentChar = 'b', count = 2

    • Write 'b' at position 2
    • Write '2' at position 3
    • Result so far: ['a','2','b','2',...]
  3. Third iteration: currentChar = 'c', count = 3

    • Write 'c' at position 4
    • Write '3' at position 5
    • Final result: ['a','2','b','2','c','3']

The method returns write = 6, indicating the compressed length.

Key Insights

  • In-place modification: The algorithm modifies the input array directly, saving space
  • Two-pointer technique: Separating read and write operations prevents data corruption
  • Handle multi-digit counts: Converting count to string handles cases where characters repeat 10+ times
  • Time complexity: O(n) - each character is read once
  • Space complexity: O(1) - only using a few extra variables

This approach efficiently compresses the string while maintaining the original array structure and returning the new length.

0
Subscribe to my newsletter

Read articles from Anni Huang directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Anni Huang
Anni Huang

I’m Anni Huang, an AI researcher-in-training currently at ByteDance, specializing in LLM training operations with a coding focus. I bridge the gap between engineering execution and model performance, ensuring the quality, reliability, and timely delivery of large-scale training projects.