Command Palette

Search for a command to run...

Hectal
Problem 3.4 · StringsMedium

String Compression

PatternTwo Pointers: Read and Write

What it teaches: A read pointer finds each run while a write pointer writes the compressed form into the same array.

Practise it on judges as “String Compression”.

The problem

Given a char[] chars, compress it in place: each run of a repeated character becomes the character followed by the run length (only if the length is more than 1). Lengths of 10 or more take several characters ("12" is '1', '2'). Return the new length; the first that many characters of chars must hold the compressed result.

Example 1

Input: chars = [a, a, b, b, c, c, c]
Output: 6

chars starts with [a, 2, b, 2, c, 3].

Example 2

Input: chars = [a]
Output: 1

Example 3

Input: chars = [a, b, b, b, b, b, b, b, b, b, b, b, b]
Output: 4

[a, b, 1, 2]: twelve b's.

Constraints

  • 1 ≤ chars.length ≤ 2000
  • O(1) extra space

Pattern clues in the wording

  • → In-place rewrite where the output is never longer than the input read so far
  • → Runs of equal neighbours

These clues point to Two Pointers: Read and Write: A fast pointer reads every element and a slow pointer marks where the next kept element should be written.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 0;
        return write;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
chars = ["a","a","b","b","c","c","c"]
6
2
chars = ["a"]
1
3
chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
4

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: read and write pointers · O(n)
1

Optimal: read and write pointers

Time O(n) Space O(1)

read starts a run at index start and advances while characters match. Write the run's character at write. If the run length is above 1, write each digit of the length. The compressed form of a run (1 char plus at most its digits) is never longer than the run, so write stays at or behind read.

▶ Dry run: Compressing runs in placechars = [a, a, b, b, c, c, c]
a
0
↑w↑r
a
1
b
2
b
3
c
4
c
5
c
6

Step 1/4First run: 'a' twice (indexes 0..1).

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

Verdict: Single pass, in place.

Before you submit

Edge cases and common mistakes

Test these inputs

  • A single character
  • No repeats at all
  • A run of 10 or more (multi-digit count)
  • The whole array is one run

Mistakes people make

  • Writing the count as one char (e.g. (char) 12) instead of its digits.
  • Writing "1" for single characters.
  • Forgetting to write the last run after the loop (avoided here by handling each run fully inside the loop).

Interview

Follow-up questions

How would you decompress?