English
443. String Compression
Problem Statement
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 tos
. - 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".```
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= chars.length <= 2000</code></li>
<li><code>chars[i]</code> is a lowercase English letter, uppercase English letter, digit, or symbol.</li>
</ul>
::: details _Click to open Hints_
- How do you know if you are at the end of a consecutive group of characters?
:::
## Solution:
::: code-group
```rs [Rust]
impl Solution {
pub fn compress(chars: &mut Vec<char>) -> i32 {
let (mut i, n) = (0, chars.len());
let mut new_len = 0;
while i < n {
let mut j = i;
// increment j until we find a different character or reach the end
while j < n && chars[j] == chars[i] {
j += 1;
}
// place the character at the new position
// e.g. if we have aabbccc, we place a at the start of the array
chars[new_len] = chars[i];
new_len += 1;
// if the length of the group of characters is greater than 1
// i.e. suppose if new_len is 12, we need to place 12 as characters [..., '1','2', ...]
if j - i > 1 {
for c in (j - i).to_string().chars() {
chars[new_len] = c;
new_len += 1;
}
}
// place i at same position as j,
// i.e. the start of the next group of characters
i = j;
}
new_len as i32
}
}
:::
...