# String Compression

MEDIUM

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.

Follow up:
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.``````

Constraints:

• `1 <= chars.length <= 2000`
• `chars[i]` is a lower-case English letter, upper-case English letter, digit, or symbol.
```class Solution {
public int compress(char[] chars) {

if(chars == null || chars.length == 0){
return 0;
}
Queue<Character> charQ = new LinkedList<>();
Queue<Integer> freqQ = new LinkedList<>();
char prev = chars[0];
int count = 1;
for(int i = 1 ; i < chars.length ; i++){
char cur = chars[i];
if(cur == prev){
count ++;
}else{
charQ.offer(prev);
freqQ.offer(count);
prev = cur;
count = 1;
}
}
if(count > 0){
charQ.offer(prev);
freqQ.offer(count);
}
int j = 0;
while(!charQ.isEmpty()){
char cur = charQ.poll();
int freq = freqQ.poll();
chars[j++] = cur;
if(freq > 1 && freq <= 9){
chars[j++] = (char)(freq+'0');
}else if(freq >= 10){
char[] number = String.valueOf(freq).toCharArray();
for(int i = 0 ; i < number.length ; i++){
chars[j++] = number[i];
}
}
}
return j;
}
}
```

Categories: String

Tagged as: ,