MediumTwo PointersString

String Compression

1 approach, code in all languages

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 unlock the solution

See 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

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI