Is String Compression easy or hard?

String Compression is usually rated Medium because it requires careful pointer manipulation and in-place updates. The core logic is simple counting, but handling multi-digit counts and maintaining correct write positions adds complexity.

String Compression Python/Java solution

Python and Java implementations typically use two pointers: one for reading characters and another for writing the compressed output. When a group ends, the character and its count digits are written sequentially. The logic is identical across languages and runs in O(n) time with O(1) space.

How to solve String Compression in O(n)?

Traverse the array using a read pointer and detect groups of identical characters. For each group, write the character at the write pointer and append the count digits if the group length is greater than one. Each character is visited once, so the algorithm completes in O(n) time with constant extra space.

What is the best approach for String Compression?

The best approach uses the two-pointer technique to compress the array in-place. One pointer reads characters while another writes the compressed result. Each group of repeating characters is counted and written once with its frequency. This solution runs in O(n) time and O(1) extra space.

Is String Compression asked at Google/Amazon/Meta?

String manipulation and in-place array compression patterns appear frequently in interviews at companies like Amazon, Google, and Meta. Problems similar to String Compression test pointer control, careful iteration, and handling edge cases in arrays or strings.

What data structure is used in String Compression?

The problem primarily uses a character array combined with the two-pointer technique. No additional data structures are required for the optimal solution since the compression happens directly within the input array.

What is the time complexity of String Compression?

The optimal algorithm processes each character exactly once while counting consecutive groups. Because the array is scanned with a single pass using read and write pointers, the time complexity is O(n). Space complexity remains O(1) since compression happens directly inside the input array.

Description Hints 1 Solution Video 19:29

443. String Compression

Medium60.9% acceptance41 companies

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints: