## 443. String Compression

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.

Could you solve it using only `O(1)` 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".```

Example 4:

```Input: chars = ["a","a","a","b","b","a","a"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","3","b","2","a","2"].
Explanation: The groups are "aaa", "bb", and "aa". This compresses to "a3b2a2". Note that each group is independent even if two groups have the same character.
```

Constraints:

• `1 <= chars.length <= 2000`
• `chars[i]` is a lower-case English letter, upper-case English letter, digit, or symbol.

## Rust Solution

``````struct Solution;

impl Solution {
fn compress(chars: &mut Vec<char>) -> i32 {
let mut j: usize = 0;
let mut prev: Option<char> = None;
let mut count = 0;
let n = chars.len();
for i in 0..n {
if let Some(c) = prev {
if c == chars[i] {
count += 1;
} else {
j += Self::write_pair(chars, j, c, count);
prev = Some(chars[i]);
count = 1;
}
} else {
count = 1;
prev = Some(chars[i]);
}
}
if let Some(c) = prev {
j += Self::write_pair(chars, j, c, count);
}
j as i32
}

fn write_pair(chars: &mut Vec<char>, mut index: usize, c: char, mut count: usize) -> usize {
chars[index] = c;
index += 1;
if count == 1 {
return 1;
}
let mut size: usize = 0;
while count > 0 {
let d: u8 = count as u8 % 10u8 + b'0';
chars[index + size] = d as char;
size += 1;
count /= 10;
}
let mut i = index;
let mut j = index + size - 1;
while i < j {
chars.swap(i, j);
i += 1;
j -= 1;
}
1 + size
}
}

#[test]
fn test() {
let mut input: Vec<char> = [
"a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b",
]
.iter()
.map(|s| s.chars().next().unwrap())
.collect();
assert_eq!(Solution::compress(&mut input), 4);
}
``````

Having problems with this solution? Click here to submit an issue on github.