# String Compression
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/string-compression)
Canonical: https://scaleengineer.com/dsa/problems/string-compression
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [Paytm](https://scaleengineer.com/companies/paytm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [Lyft](https://scaleengineer.com/companies/lyft), [Salesforce](https://scaleengineer.com/companies/salesforce), [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe), [Pinterest](https://scaleengineer.com/companies/pinterest), [Zoox](https://scaleengineer.com/companies/zoox), [Rivian](https://scaleengineer.com/companies/rivian), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Affirm](https://scaleengineer.com/companies/affirm), [Ripple](https://scaleengineer.com/companies/ripple)
---
## Problem
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.

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

# Approaches
## Naive Approach with Extra Space
A straightforward way to solve this is to build the compressed string in an auxiliary data structure, like a `StringBuilder`, and then copy the result back into the input array. This approach is intuitive and easy to implement but fails the crucial constant extra space constraint of the problem.
**Time:** O(N), where N is the length of `chars`. The first pass to build the string takes O(N) time. The second pass to copy the result back into the array also takes O(N) time. Thus, the total time complexity is O(N). · **Space:** O(N). The `StringBuilder` can grow up to a size proportional to N. For an input like `['a', 'b', 'c', 'd']`, the compressed string is the same, requiring O(N) extra space. This violates the problem's constraint.
**Pros:** Simple to conceptualize and implement.; The logic is very clear and follows the problem description directly.
**Cons:** Violates the O(1) extra space constraint, making it an invalid solution for this specific problem.; Requires a second pass to copy the data back, which is less efficient than an in-place modification.
### Explanation
This method involves two main phases. First, we iterate through the input character array to identify groups of consecutive characters. For each group, we append the character followed by its count (if the count is greater than 1) to a `StringBuilder`. This effectively builds the compressed string in memory. In the second phase, we overwrite the original `chars` array with the content of the `StringBuilder`. The final length of the compressed string is simply the length of the `StringBuilder`.

```java
public int compress(char[] chars) {
    if (chars == null || chars.length == 0) {
        return 0;
    }
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < chars.length) {
        char currentChar = chars[i];
        int count = 0;
        int j = i;
        while (j < chars.length && chars[j] == currentChar) {
            j++;
            count++;
        }
        sb.append(currentChar);
        if (count > 1) {
            sb.append(count);
        }
        i = j;
    }
    
    char[] compressedChars = sb.toString().toCharArray();
    for (int k = 0; k < compressedChars.length; k++) {
        chars[k] = compressedChars[k];
    }
    
    return sb.length();
}
```
### Algorithm
- Initialize an empty `StringBuilder`.
- Iterate through the input `chars` array using a pointer `i`.
- For each character at `chars[i]`, find the end of the consecutive group and determine its `count`.
- Append the character to the `StringBuilder`.
- If `count` is greater than 1, append the string representation of `count` to the `StringBuilder`.
- Advance `i` to the start of the next group.
- After the loop, copy the characters from the `StringBuilder` back to the `chars` array.
- Return the length of the `StringBuilder`.

## Optimal In-place Compression with Two Pointers
The optimal solution uses a two-pointer technique to modify the array in-place, satisfying the constant extra space requirement. We use a `read` pointer to iterate through the original array and a `write` pointer to place the compressed characters. Since the compressed version is always shorter or of the same length, the `write` pointer never surpasses the `read` pointer, allowing for safe in-place modification.
**Time:** O(N), where N is the length of `chars`. Each character is read exactly once by the `readIndex`, and each character of the output is written exactly once by the `writeIndex`. The overall process is a single pass through the array. · **Space:** O(1). The algorithm uses a fixed number of variables (`writeIndex`, `readIndex`, `count`, etc.) regardless of the input size. The space used to store the string representation of a count is temporary and bounded by O(log N), which is considered constant for practical purposes and within the problem's constraints.
**Pros:** Extremely efficient, with linear time and constant space complexity.; Modifies the array in-place as required by the problem.; It's the optimal solution that meets all constraints.
**Cons:** The in-place logic with two pointers can be slightly more complex to grasp initially compared to using an auxiliary data structure.
### Explanation
This algorithm processes the array in a single pass. We maintain two pointers: `readIndex` and `writeIndex`. The `readIndex` scans the array from left to right to identify groups of consecutive characters. The `writeIndex` points to the next available slot in the `chars` array where the compressed data should be written. For each group, we first write the character itself. Then, if the group's length is greater than one, we convert the length to its character digits and write them sequentially. The `readIndex` is advanced to the beginning of the next group, and the process repeats. The final value of `writeIndex` gives the new length of the array.

```java
public int compress(char[] chars) {
    int writeIndex = 0;
    int readIndex = 0;
    
    while (readIndex < chars.length) {
        char currentChar = chars[readIndex];
        int count = 0;
        
        // Count consecutive repeating characters
        while (readIndex < chars.length && chars[readIndex] == currentChar) {
            readIndex++;
            count++;
        }
        
        // Write the character
        chars[writeIndex++] = currentChar;
        
        // If count > 1, write the count as characters
        if (count > 1) {
            for (char c : String.valueOf(count).toCharArray()) {
                chars[writeIndex++] = c;
            }
        }
    }
    
    return writeIndex;
}
```
### Algorithm
- Initialize `writeIndex = 0` and `readIndex = 0`.
- Loop while `readIndex` is less than the array length.
- Inside the loop, identify the current character and count its consecutive occurrences, advancing `readIndex` past the group.
- Write the character to `chars[writeIndex]` and increment `writeIndex`.
- If the group's count is greater than 1, convert the count to a string.
- For each digit in the count string, write it to `chars[writeIndex]` and increment `writeIndex`.
- After the loop finishes, `writeIndex` holds the new length of the compressed array. Return `writeIndex`.

# Solutions
### Java

```java
class Solution {
public
  int compress(char[] chars) {
    int k = 0, n = chars.length;
    for (int i = 0, j = i + 1; i < n;) {
      while (j < n && chars[j] == chars[i]) {
        ++j;
      }
      chars[k++] = chars[i];
      if (j - i > 1) {
        String cnt = String.valueOf(j - i);
        for (char c : cnt.toCharArray()) {
          chars[k++] = c;
        }
      }
      i = j;
    }
    return k;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int compress(vector<char> &chars) {
    int k = 0, n = chars.size();
    for (int i = 0, j = i + 1; i < n;) {
      while (j < n && chars[j] == chars[i])
        ++j;
      chars[k++] = chars[i];
      if (j - i > 1) {
        for (char c : to_string(j - i)) {
          chars[k++] = c;
        }
      }
      i = j;
    }
    return k;
  }
};

```

### Python

```python
class Solution:
    def compress(self, chars: List[str]) -> int: i, k, n = 0, 0, len(chars) while i < n: j = i + 1 while j < n and chars[j] == chars[i]: j += 1 chars[k] = chars[i] k += 1 if j - i > 1: cnt = str(j - i) for c in cnt: chars[k] = c k += 1 i = j return k ''' if a follow up question asking for the compressed result, simply return return chars[:k]; '''

```