String Compression

mediumFREEArrays & StringsMicrosoft DSA

Given an array of characters, compress it in-place using consecutive counts. Single characters stay as-is, runs become char + count. Return the new length.

Output the compressed array as space-separated characters.

Example

Input

a,a,b,b,c,c,c

Output

a 2 b 2 c 3

Reasoning

The input array is iterated through to identify consecutive runs of characters: a,a is one run, b,b is another, and c,c,c is the last.
Each run is replaced by the character and its count: a,a becomes a 2, b,b becomes b 2, and c,c,c becomes c 3.
The compressed array elements are then output as space-separated values: a 2 b 2 c 3.
The new length of the compressed array is the total count of elements, which in this case is $6$ (since there are $6$ space-separated values), but the problem only asks for the compressed array, not the length.
The resulting compressed array is output as the final result.

Constraints

1 <= len(chars) <= 2000
chars[i] is a letter, digit, or symbol

More from Microsoft DSA

FizzBuzzeasy Roman to Integereasy Reverse Integermedium Pow(x, n)medium Implement Stack using Queueseasy

Concept primer

Background Knowledge

The problem of string compression involves reducing the size of a given string by representing consecutive repeated characters as a single character followed by the count of repetitions. This is a common technique used in data compression and encoding. To approach this problem, it's essential to understand the concept of in-place modification, where the original array is modified directly without creating a new one. Additionally, familiarity with array traversal and character manipulation is necessary.

The key concept here is to identify runs of consecutive characters in the array. A run is a sequence of identical characters. By replacing each run with the character and its count, we can achieve compression. For example, the array ['a', 'a', 'b', 'b', 'b', 'c'] can be compressed to ['a', '2', 'b', '3', 'c']. Understanding how to iterate through the array, identify runs, and modify the array in-place is crucial.

In the context of arrays and strings, it's also important to consider the indexing and bounds of the array. Since the problem requires in-place modification, we need to be mindful of the array's length and how it changes as we compress the string. The new length of the compressed array will be the final output, which requires careful calculation to ensure accuracy.

Algorithm/Approach

The general approach to solving this problem involves using a two-pointer technique. One pointer can be used to track the current character, while the other pointer can be used to track the next character. By comparing the characters at these two pointers, we can identify runs of consecutive characters. Additionally, we can use a count variable to keep track of the length of each run. This approach allows us to iterate through the array efficiently and modify it in-place.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize two pointers, one at the beginning of the array and one at the second character.
Compare the characters at the two pointers. If they are the same, increment the count and move the second pointer forward.
If the characters are different, replace the run of characters with the character and its count, and update the pointers accordingly.
Continue this process until the end of the array is reached.
Calculate the new length of the compressed array.

Common Pitfalls

When implementing the solution, watch out for:

Incorrectly updating the pointers, leading to incorrect compression.
Failing to handle the case where a character appears only once.
Not properly calculating the new length of the compressed array.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the length of the input array, since we only need to iterate through the array once. The space complexity is $O(1)$ , since we are modifying the array in-place and not using any additional data structures that scale with the input size.

solution.py

Python 3.13

Test results