MediumTwo PointersString

String Compression

1 approach, code in every language

You are given an array of single characters and asked to compress it in place using run-length encoding. For each block of consecutive equal characters, write the character once, and if the block is longer than one, follow it with the decimal digits of the block's length.

Perform the rewrite inside the same array and return the length of the compressed section. You may use only constant extra space beyond the input array itself.

Example 1

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

Output: 6

The runs "aa", "bb", and "ccc" compress to a2, b2, c3. The first six slots become ['a','2','b','2','c','3'] and the function returns 6.

Example 2

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

Output: 3

A run of twelve 'a' characters compresses to the three slots ['a','1','2'], since the count 12 is spelled out digit by digit.

Constraints

1 <= chars.length <= 2000
chars[i] is a lowercase letter, uppercase letter, digit, or symbol
The compressed result always fits within the original array

Read And Write Pointers

Use one pointer to measure each run of equal characters and a second pointer to write the character and its run length back into the array.

Loading animation…

Intuition

Because the compressed output is never longer than the input, you can overwrite the array in place as you go. Keep a read pointer that races ahead to count how long the current run of identical characters is, and a write pointer that records the results. For every run you write the character, and when the run has more than one member you append the count as individual digit characters. The write pointer's final position is the compressed length.

Algorithm walkthrough

1Set a read pointer and a write pointer both to the start of the array.
2At each run, remember the current character and advance the read pointer while it keeps matching, counting the run length.
3Write the run's character at the write pointer and advance it.
4If the run length exceeds one, write each digit of the count and advance the write pointer for each.
5Repeat until the read pointer passes the end, then return the write pointer's value.

Implementation

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0
        read = 0
        n = len(chars)
        while read < n:
            ch = chars[read]
            count = 0
            while read < n and chars[read] == ch:
                read += 1
                count += 1
            chars[write] = ch
            write += 1
            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1
        return write

Time

O(n)

Space

O(1)

Each character is read and written a constant number of times; the rewrite happens inside the input array.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Pack the Symbol Tape is our own problem on the technique behind String Compression: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free