String Compression

Medium Arrays & Hashing Two Pointer Original on LeetCode

String Compression is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (read and write pointers in place), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from build a new string, then copy back up.

Problem

You are given an array of characters chars. Compress it in place using run-length encoding: every maximal run of equal consecutive characters is replaced by the character itself, followed by the run’s length written in decimal digits. A run of length 1 is written as just the character, with no count. A run of 12 contributes the separate characters '1' and '2'.

Write the compressed result into the beginning of chars and return its length k. Only chars[0..k-1] is checked; whatever remains after it does not matter. Use only constant extra memory.

Examples

Example 1

Input
chars = ["x", "x", "y", "z", "z", "z"]
Output
5, chars starts with ["x", "2", "y", "z", "3"]
Why
The runs are xx, y and zzz. A run of length 1 keeps only its character.

Example 2

Input
chars = ["q"]
Output
1, chars starts with ["q"]
Why
A single character is already as short as it gets.

Example 3

Input
chars = ["m", "m", "m", "m", "m", "m", "m", "m", "m", "m", "m", "m", "k"]
Output
4, chars starts with ["m", "1", "2", "k"]
Why
Twelve m's become m followed by the two digits 1 and 2.

Constraints

  • 1 <= chars.length <= 2000
  • chars[i] is an English letter, a digit or a symbol.
  • Use only O(1) extra memory.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Build a new string, then copy backO(n)O(n)
Optimal (read and write pointers in place)O(n)O(1)

1Build a new string, then copy back

TimeO(n)Every character is read once and every output character is written twice.
SpaceO(n)The builder can hold up to n characters, breaking the O(1) memory rule.

Scan the runs and append each run's character and count to a separate string builder. Then copy the builder into the front of the array and return its length.

  1. i = 0; while i < n: find j, the first index after i whose character differs.
  2. Append chars[i]; if j - i > 1, append the decimal digits of j - i.
  3. Set i = j.
  4. Copy the builder into chars[0..] and return its length.
class Solution {
    public int compress(char[] chars) {
        StringBuilder sb = new StringBuilder();
        int i = 0, n = chars.length;
        while (i < n) {
            int j = i;
            while (j < n && chars[j] == chars[i]) j++;
            sb.append(chars[i]);
            if (j - i > 1) sb.append(j - i);
            i = j;
        }
        for (int k = 0; k < sb.length(); k++) chars[k] = sb.charAt(k);
        return sb.length();
    }
}

2Optimal (read and write pointers in place)

TimeO(n)The read pointer passes each index once; the writes are at most n.
SpaceO(1)Only a few integer variables; the digits are written straight into the array.

Use a read pointer to walk over runs and a write pointer for the compressed output in the same array. The output for a run (1 character plus at most 4 digits) is never longer than the run's own length, so the write pointer never passes the read pointer and nothing unread is overwritten.

  1. write = 0, read = 0.
  2. While read < n: c = chars[read]; count the run by advancing read while chars[read] == c.
  3. chars[write++] = c.
  4. If the run length is more than 1, write each digit of the length at chars[write++].
  5. Return write.
class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 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 len = read - start;
            if (len > 1) {
                for (char d : Integer.toString(len).toCharArray()) {
                    chars[write++] = d;
                }
            }
        }
        return write;
    }
}

Edge cases to test

  • A single character
  • No repeated characters at all: nothing changes and the length stays n
  • A run of 10 or more: its count takes several characters
  • The same character in two separate runs, like a a b a, is compressed run by run

Hints

Hint 1

Process the array run by run: find where the current run of equal characters ends.

Hint 2

The compressed text is never longer than the part of the array you have already read, so you can write it into the same array.

Hint 3

Keep a read pointer and a write pointer. For each run write the character, then (if the run is longer than 1) the digits of its length.

FAQ

What is the best time complexity for String Compression?

Optimal (read and write pointers in place) runs in O(n) time and O(1) extra space. The read pointer passes each index once; the writes are at most n.

Which pattern does String Compression use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for String Compression?

Yes. Build a new string, then copy back takes O(n) time and O(n) space. Scan the runs and append each run's character and count to a separate string builder.

Which edge cases should I test for String Compression?

A single character; No repeated characters at all: nothing changes and the length stays n; A run of 10 or more: its count takes several characters; The same character in two separate runs, like a a b a, is compressed run by run.