Skip to main content
CodePeet

String Compression

Try it yourself
MediumProblemExternal link

Description

You get an array of characters chars. Compress it group by group, where a group is a run of the same character next to each other:

  • A group of one is written as just its character.
  • A longer group is written as its character followed by its length.

A length of 10 or more takes one seat per digit: a group of 12 is written as the character, then "1", then "2".

Write the compressed result into chars itself and return its length k. Use only O(1) extra space.

How it's checked: the judge reads k, then compares the first k characters of chars with the expected ones.

Examples

Example 1

Input: chars = ["a", "a", "b", "b", "c", "c", "c"]

Output: 6, chars = ["a", "2", "b", "2", "c", "3", _]

Explanation: Three groups: a twice, b twice, c three times. Each becomes its letter and its count, so the first six seats hold a, 2, b, 2, c, 3 and k = 6.

Example 2

Input: chars = ["a"]

Output: 1, chars = ["a"]

Explanation: A group of one is written as just the character, with no count. k = 1.

Example 3

Input: chars = ["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"]

Output: 4, chars = ["a", "b", "1", "2", _, _, _, _, _, _, _, _, _]

Explanation: a appears once, so it stays alone. b appears 12 times, and 12 is written as two characters, "1" then "2". k = 4.

Constraints

  • 1 ≤ chars.length ≤ 2000
  • chars[i] is a lowercase English letter, an uppercase English letter, a digit, or a symbol

Editorial

Brute Force

Intuition

Do exactly what the rule says, on the side. Walk the array one group at a time, and write each group's character, plus its length when it's longer than one, into a separate result. Then copy the result back into the front of chars.

It's simple and correct. The only problem is the separate result: the task asks for O(1) extra space.

Step-by-Step Explanation

Let's trace chars = ["a", "a", "b", "b", "c", "c", "c"]:

  1. Seats 0 to 1 are a group of 2 × "a": write "a" and "2".
  2. Seats 2 to 3 are a group of 2 × "b": write "b" and "2".
  3. Seats 4 to 6 are a group of 3 × "c": write "c" and "3".

The result is ["a", "2", "b", "2", "c", "3"]. Copy it back and return k = 6.

Compress Into a Separate Result — Each group of the top row is written into the bottom row as its character and count.

Algorithm

  1. Create an empty result.
  2. For each group chars[i..j) of one character:
    • append chars[i];
    • if j - i > 1, append the digits of j - i.
  3. Copy the result into the front of chars and return its length.

Code

class Solution {
public:
    int compress(vector<char>& chars) {
        string out;                                   // the compressed result, built on the side
        int i = 0, n = chars.size();
        while (i < n) {
            int j = i;
            while (j < n && chars[j] == chars[i]) j++;   // chars[i .. j) is one group
            out += chars[i];
            if (j - i > 1) out += to_string(j - i);
            i = j;
        }
        for (int k = 0; k < (int)out.size(); k++) chars[k] = out[k];   // copy it back
        return out.size();
    }
};

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        out = []                                  # the compressed result, built on the side
        i = 0
        while i < len(chars):
            j = i
            while j < len(chars) and chars[j] == chars[i]:
                j += 1                            # chars[i:j] is one group
            out.append(chars[i])
            if j - i > 1:
                out.extend(str(j - i))
            i = j
        chars[:len(out)] = out                    # copy it back
        return len(out)

class Solution {
    public int compress(char[] chars) {
        StringBuilder out = new StringBuilder();       // the compressed result, built on the side
        int i = 0, n = chars.length;
        while (i < n) {
            int j = i;
            while (j < n && chars[j] == chars[i]) j++;    // chars[i .. j) is one group
            out.append(chars[i]);
            if (j - i > 1) out.append(j - i);
            i = j;
        }
        for (int k = 0; k < out.length(); k++) chars[k] = out.charAt(k);   // copy it back
        return out.length();
    }
}

var compress = function(chars) {
    const out = [];                                   // the compressed result, built on the side
    let i = 0;
    while (i < chars.length) {
        let j = i;
        while (j < chars.length && chars[j] === chars[i]) j++;   // chars[i .. j) is one group
        out.push(chars[i]);
        if (j - i > 1) out.push(...String(j - i));
        i = j;
    }
    for (let k = 0; k < out.length; k++) chars[k] = out[k];   // copy it back
    return out.length;
};

Complexity Analysis

Time Complexity: O(n)

Each character is read once, and the result is at most n characters long.

Space Complexity: O(n)

With no repeats at all, the result is a full copy of chars.

Why This Approach Is Not Efficient

Time isn't the issue: it's already O(n). The separate result is: it can hold n characters, and the task allows O(1) extra space.

Can the result live in chars itself? Only if writing it never overwrites characters you haven't read yet. Look at how long each group is when written:

  • a group of 1 takes 1 seat;
  • a group of c ≥ 2 takes 1 seat for the character plus 1 seat per digit of c, and that's never more than c (2 → 2 seats, 9 → 2, 10 → 3, 100 → 4).

So the compressed form of everything you've read is never longer than what you've read. Write it at the front, behind the reader, and nothing unread is ever lost.

Optimal Approach - Two Pointers

Intuition

Use chars itself for the result. Keep two indexes:

  • read walks a whole group at a time.
  • write is the next seat of the compressed result at the front.

For each group, write its character at write, then the digits of its length if it's longer than one. Because a group never takes more seats written than it had, write stays at or behind read, and every seat it writes over has already been read.

Step-by-Step Explanation

Let's trace chars = ["a", "a", "b", "b", "c", "c", "c"]:

  1. read covers seats 0 to 1, a group of 2 × "a": write ["a", "2"] into seats 0 to 1. write = 2.
  2. read covers seats 2 to 3, a group of 2 × "b": write ["b", "2"] into seats 2 to 3. write = 4.
  3. read covers seats 4 to 6, a group of 3 × "c": write ["c", "3"] into seats 4 to 5. write = 6.

Result: k = 6, and the first 6 seats hold ["a", "2", "b", "2", "c", "3"]. The last seat still holds the "c" it started with; it's ignored.

Read a Group, Write Its Character and Count — read covers one group at a time; its character and count are written at the front, where violet seats are the answer so far.

Algorithm

  1. Set write = 0 and read = 0.
  2. While read < n:
    • remember start = read, and move read to the end of the group;
    • set chars[write] = chars[start] and add 1 to write;
    • if the group is longer than one, write each digit of read - start at write, adding 1 each time.
  3. Return write.

Code

class Solution {
public:
    int compress(vector<char>& chars) {
        int write = 0, read = 0, n = chars.size();
        while (read < n) {
            int start = read;
            while (read < n && chars[read] == chars[start]) read++;   // read the whole group
            chars[write++] = chars[start];
            int count = read - start;
            if (count > 1) {
                for (char digit : to_string(count)) chars[write++] = digit;   // 12 is written as '1', '2'
            }
        }
        return write;
    }
};

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = read = 0
        while read < len(chars):
            start = read
            while read < len(chars) and chars[read] == chars[start]:
                read += 1                      # read the whole group
            chars[write] = chars[start]
            write += 1
            count = read - start
            if count > 1:
                for digit in str(count):       # 12 is written as "1", "2"
                    chars[write] = digit
                    write += 1
        return write

class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 0;
        while (read < chars.length) {
            int start = read;
            while (read < chars.length && chars[read] == chars[start]) read++;   // read the whole group
            chars[write++] = chars[start];
            int count = read - start;
            if (count > 1) {
                for (char digit : Integer.toString(count).toCharArray()) chars[write++] = digit;   // 12 → '1', '2'
            }
        }
        return write;
    }
}

var compress = function(chars) {
    let write = 0, read = 0;
    while (read < chars.length) {
        const start = read;
        while (read < chars.length && chars[read] === chars[start]) read++;   // read the whole group
        chars[write++] = chars[start];
        const count = read - start;
        if (count > 1) {
            for (const digit of String(count)) chars[write++] = digit;      // 12 is written as "1", "2"
        }
    }
    return write;
};

Complexity Analysis

Time Complexity: O(n)

read passes each character once, and the writes are never more than the reads.

Space Complexity: O(1)

A few integers. Turning a count into digits takes at most 4 characters here (n ≤ 2000).

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Writing a count for a group of one. for digit in str(read - start):

On chars = ["b", "b", "b", "a"] it returns k = 4 with ["b", "3", "a", "1"] in front; the answer is k = 3 with ["b", "3", "a"] in front. A group of one is written as just its character. Writing "1" after it makes the result longer than the input, which is the opposite of compressing.

Writing the count into one seat. chars[write] = str(read - start)

On chars = ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a"] it returns k = 2 with ["a", "10"] in front; the answer is k = 3 with ["a", "1", "0"] in front. A count of 10 or more has two or more digits, and each digit needs its own seat. Putting the whole count in one seat (in Java or C++, (char)('0' + count)) is only right for counts up to 9.

Forgetting the last group. return write

On chars = ["a", "a", "b"] it returns k = 2 with ["a", "2"] in front; the answer is k = 3 with ["a", "2", "b"] in front. Writing a group only when the next character is different never writes the last group, because nothing comes after it. The loop needs one more write after it ends.

Where This Pattern Is Taught

This problem practises same-direction two pointers: one reads, one writes. It's taught in Same-Direction Two Pointers: Changing an Array in Place. The difference here is that the writer writes a whole group's summary, not one value, and it's still safe because the summary is never longer than the group.