LeetCode 443: String Compression

Problem Restatement

We are given an array of characters:

chars

We must compress the array in-place using these rules:

For example:

["a","a","b","b","c","c","c"]

becomes:

["a","2","b","2","c","3"]

The compressed result must be written back into the same array.

The function returns the new length after compression.

Counts larger than 9 must be split into multiple characters.

For example:

12

must be written as:

"1", "2"

The official problem asks for in-place compression with constant extra space. (leetcode.com)

Input and Output

Example function shape:

def compress(chars: list[str]) -> int:
    ...

Examples

Example 1:

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

Compression groups:

Compressed array:

["a","2","b","2","c","3"]

Returned length:

6

Example 2:

chars = ["a"]

Single characters keep only themselves.

Compressed array:

["a"]

Returned length:

1

Example 3:

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

There are:

12

copies of "b".

Compressed array becomes:

["a","b","1","2"]

Returned length:

4

First Thought: Build a New String

We could create another array:

result = []

Then append compressed groups into it.

This is simple, but the problem requires in-place modification with constant extra space.

So we must overwrite the original array directly.

Key Insight

Compression happens group by group.

For example:

a a a b b c

contains groups:

aaa
bb
c

We can process each group independently.

Use two pointers:

We also keep a write pointer:

write

which tells where to place compressed output.

For each group:

1. Write the character.
2. Compute the group size.
3. If size > 1, write the digits of the count.

Algorithm

Initialize:

write = 0
i = 0

While i < len(chars):

1. Find the maximal group starting at i.
2. Let j be the first index after the group.
3. Group size:

count = j - i

4. Write the character at position write.
5. Increase write.
6. If count > 1:
   • Convert count to string.
   • Write each digit into the array.
7. Move:

i = j

At the end, return write.

Correctness

At every iteration, the algorithm processes exactly one maximal contiguous group of equal characters.

Suppose the current group contains:

count

copies of character c.

The compression rules require:

The algorithm writes exactly this representation.

The write pointer always points to the next unused position in the compressed prefix of the array. Therefore, writing the compressed representation overwrites old data safely without losing unprocessed characters, because the read pointer i and scanning pointer j always stay ahead.

After processing a group, the algorithm advances i to the first unprocessed character.

Thus every group is compressed exactly once, and the final prefix:

chars[:write]

contains the required compressed array.

Therefore, returning write gives the correct compressed length.

Complexity

Implementation

class Solution:
    def compress(self, chars: list[str]) -> int:
        write = 0
        i = 0
        n = len(chars)

        while i < n:
            j = i

            while j < n and chars[j] == chars[i]:
                j += 1

            count = j - i

            chars[write] = chars[i]
            write += 1

            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1

            i = j

        return write

Code Explanation

We use:

write = 0

to track where compressed output should be written.

The pointer:

i = 0

marks the start of the current group.

For every group, we extend:

j

while characters remain equal:

while j < n and chars[j] == chars[i]:

Then:

count = j - i

is the group size.

We always write the group character:

chars[write] = chars[i]
write += 1

If the group size exceeds one:

if count > 1:

we write every digit of the count:

for digit in str(count):

This handles counts larger than 9.

Finally, we move to the next group:

i = j

At the end, write equals the compressed length.

Testing

def compressed(chars):
    s = Solution()
    length = s.compress(chars)
    return chars[:length]

def run_tests():
    assert compressed(
        ["a","a","b","b","c","c","c"]
    ) == ["a","2","b","2","c","3"]

    assert compressed(
        ["a"]
    ) == ["a"]

    assert compressed(
        ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
    ) == ["a","b","1","2"]

    assert compressed(
        ["a","a","a","a"]
    ) == ["a","4"]

    assert compressed(
        ["a","b","c"]
    ) == ["a","b","c"]

    assert compressed(
        ["z"] * 15
    ) == ["z","1","5"]

    print("all tests passed")

run_tests()

Test meaning: