# 0443 - String Compression (Medium)

## Problem Link

https://leetcode.com/problems/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 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.

Given an integer array `nums`

, return `true`

*if there exists a triple of indices* `(i, j, k)`

*such that* `i < j < k`

*and* `nums[i] < nums[j] < nums[k]`

. If no such indices exists, return `false`

.

**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:**

`1 <= chars.length <= 2000`

`chars[i]`

is a lowercase English letter, uppercase English letter, digit, or symbol.

**Follow up:** Could you implement a solution that runs in `O(n)`

time complexity and `O(1)`

space complexity?

## Approach 1: Iterative

As stated in the problem, find the **consecutive repeating characters** frequency and once a **set of group is found** then modify the array with the character, number of occurances in the next index and repeat the process till last.

Since it's input is a char array, if number of occurrance for a character is more than 9 times, place the numbers in an invididual position and move forward.

- Java

`class Solution {`

public int compress(char[] chars) {

int i = 0, res = 0;

while (i < chars.length) {

int groupLength = 1;

while (i + groupLength < chars.length && chars[i + groupLength] == chars[i]) {

groupLength += 1;

}

chars[res++] = chars[i];

if (groupLength > 1) {

for (char c : Integer.toString(groupLength).toCharArray()) {

chars[res++] = c;

}

}

i += groupLength;

}

return res;

}

}