Problem Explanation

In this problem, we are given an array of characters and we need to compress the array in-place by replacing consecutive repeating characters with the count of those characters.

Walkthrough

For example, let's use an input array as ["a","a","b","b","c","c","c"]. The expected output will be 6 and the first six characters of the new array should be ["a","2","b","2","c","3"] because "aa" gets compressed to "a2", "bb" to "b2", and "ccc" to "c3".

Approach

We can solve the problem by utilizing a two-pointer type technique to count the repeating characters. The first pointer will point to the character we are currently reading and the second pointer will point to the position of the next character to be overwritten.

Firstly, we will initialize both pointers to the first character. Then, we will move the first pointer to scan through the array. If a consecutive repetition of a character has been found, increase the counter. After we finish counting a group of characters, we will write the result to the position pointed by the second pointer. Secondly, we will convert the count to a string, and then copy the digits into the array, one digit at a time.

After all groups are scanned and written, the second pointer will be the new length of the array.

Example

Let's use the example ["a","a","b","b","c","c","c"], and we will initialize the variables:

• i(pointer_1)=0, j=0(pointer_2), chars=[].

Iterate through the array:

• 1st Iteration: 'a' is repeated twice, so i becomes 2 and we append 'a' and '2' to chars, making chars = ['a', '2'] and j becomes 2.
• 2nd Iteration: 'b' is repeated twice, so i becomes 4 and we append 'b' and '2' to chars, making chars = ['a', '2', 'b', '2'] and j becomes 4.
• 3rd Iteration: 'c' is repeated thrice, so i becomes 7 and we append 'c' and '3' to chars, making chars = ['a', '2', 'b', '2', 'c', '3'] and j becomes 6.

Finally, since there are no more characters, return j(=6) as the new length.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int compress(vector<char>& chars) {
6    int ans = 0;
7    for (int i = 0; i < chars.size();) {
8      const char letter = chars[i];
9      int count = 0;
10      while (i < chars.size() && chars[i] == letter) {
11        ++count;
12        ++i;
13      }
14      chars[ans++] = letter;
15      if (count > 1)
16        for (const char c : to_string(count))
17          chars[ans++] = c;
18    }
19    return ans;
20  }
21};

Python Solution

1
2python
3class Solution:
4    def compress(self, chars: List[str]) -> int:
5        j = 0
6        i = 0
7        while i < len(chars):
8            chars[j] = chars[i]
9            count = 0
10            while i < len(chars) and chars[j] == chars[i]:
11                i += 1
12                count += 1
13            if count > 1:
14                for c in str(count):
15                    j += 1
16                    chars[j] = c
17            j += 1
18        return j

Java Solution

1
2java
3class Solution {
4    public int compress(char[] chars) {
5        int j = 0;
6        int i = 0;
7        while (i < chars.length) {
8            chars[j] = chars[i];
9            int count = 0;
10            while (i < chars.length && chars[j] == chars[i]) {
11                i++;
12                count++;
13            }
14            if (count > 1) {
15                for (char c : Integer.toString(count).toCharArray()) {
16                    j++;
17                    chars[j] = c;
18                }
19            }
20            j++;
21        }
22        return j;
23    }
24}

JavaScript Solution

1
2javascript
3var compress = function(chars) {
4    let i = 0;
5    let j = 0;
6    while(i < chars.length){
7        let currentChar = chars[i];
8        let count = 0;
9        while(chars[i] === currentChar){
10            i++;
11            count++;
12        }
13        chars[j++] = currentChar;
14        if(count > 1){
15            let countArr = String(count).split('');
16            for(let k = 0; k < countArr.length; k++){
17                chars[j++] = countArr[k];
18            }
19        }
20    }
21    return j;
22};

C# Solution

1
2csharp
3public class Solution {
4    public int Compress(char[] chars) {
5        int i = 0, j = 0;
6        while (i < chars.Length) {
7            char currentChar = chars[i];
8            int count = 0;
9            while ( i < chars.Length && chars[i] == currentChar) {
10                i++;
11                count++;
12            }
13            chars[j++] = currentChar;
14            if (count > 1) {
15                foreach (char c in count.ToString()) {
16                    chars[j++] = c;
17                }
18            }
19        }
20        return j;
21    }
22}

Each solution is using the two-pointer approach. Pointer i is used to scan through the characters array, and pointer j is used to write the character and the count in it's place.All solutions also ensure that if the count of the character is greater than 1, they convert the count to its string representation and append the count at the same position consecutively.

Furthermore, these solutions work in O(n) time complexity where n is the length of the array. This is because each character in the array is read and written at most once.

In terms of space complexity, the solutions use O(1) auxiliary space. This means they don't use any additional space proportional to the size of the input, making them in-place solutions. The solutions only utilize a couple of extra variables for counting and pointers.

The function then returns the new length of the compressed array. If you need to get the new string, in Python, you can simply join the characters using chars[:j].

In general, whether you're working with Python, Java, JavaScript, C++, or C#, you can easily implement this solution using the two-pointer technique and basic string manipulation methods. It's a handy technique to keep in your toolkit for handling similar string or array compression tasks.