# String Compression III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/string-compression-iii)
Canonical: https://scaleengineer.com/dsa/problems/string-compression-iii
**Data structures:** String
**Companies:** [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Affirm](https://scaleengineer.com/companies/affirm)
---
## Problem
Given a string `word`, compress it using the following algorithm:

* Begin with an empty string `comp`. While `word` is **not** empty, use the following operation:  
  * Remove a maximum length prefix of `word` made of a _single character_ `c` repeating **at most** 9 times.
  * Append the length of the prefix followed by `c` to `comp`.

Return the string `comp`.

**Example 1:**

**Input:** word = "abcde"

**Output:** "1a1b1c1d1e"

**Explanation:**

Initially, `comp = ""`. Apply the operation 5 times, choosing `"a"`, `"b"`, `"c"`, `"d"`, and `"e"` as the prefix in each operation.

For each prefix, append `"1"` followed by the character to `comp`.

**Example 2:**

**Input:** word = "aaaaaaaaaaaaaabb"

**Output:** "9a5a2b"

**Explanation:**

Initially, `comp = ""`. Apply the operation 3 times, choosing `"aaaaaaaaa"`, `"aaaaa"`, and `"bb"` as the prefix in each operation.

* For prefix `"aaaaaaaaa"`, append `"9"` followed by `"a"` to `comp`.
* For prefix `"aaaaa"`, append `"5"` followed by `"a"` to `comp`.
* For prefix `"bb"`, append `"2"` followed by `"b"` to `comp`.

**Constraints:**

* `1 <= word.length <= 2 * 105`
* `word` consists only of lowercase English letters.

# Approaches
## Naive Simulation with Substrings
This approach directly implements the logic described in the problem statement. It works by repeatedly identifying the next chunk to compress, appending its compressed form to the result, and then creating a new, shorter string for the remaining part of the word. This process is repeated until the entire string is consumed.
**Time:** O(N^2), where N is the length of `word`. The `substring` operation is the bottleneck. In each iteration of the `while` loop, creating a substring takes time proportional to the length of the new string. In the worst-case scenario (e.g., a string with no repeating characters like 'abcde'), the loop runs N times, and the substring operations result in a quadratic time complexity. · **Space:** O(N^2) in the worst case. Although the final output string is O(N), the cumulative space for all intermediate substrings created during the loop can be quadratic. For an input of length N, strings of length approximately N-1, N-2, ..., 1 are created.
**Pros:** Very straightforward to implement as it's a direct translation of the problem description.
**Cons:** Highly inefficient with a time complexity of O(N^2) in the worst case.; Creates many temporary string objects, leading to high memory usage and garbage collector overhead.; Likely to fail on large inputs with a 'Time Limit Exceeded' (TLE) error.
### Explanation
This method simulates the compression process step-by-step as described. While conceptually simple because it's a literal translation of the problem, it suffers from significant performance issues due to the way strings are handled in many programming languages like Java, where they are immutable. The repeated creation of new substrings is a costly operation.

```java
class Solution {
    public String compressedString(String word) {
        StringBuilder comp = new StringBuilder();
        String currentWord = word;
        while (!currentWord.isEmpty()) {
            char c = currentWord.charAt(0);
            int count = 0;
            while (count < currentWord.length() && currentWord.charAt(count) == c) {
                count++;
            }
            
            int chunkSize = Math.min(count, 9);
            comp.append(chunkSize);
            comp.append(c);
            
            currentWord = currentWord.substring(chunkSize);
        }
        return comp.toString();
    }
}
```
### Algorithm
- Initialize `comp` as an empty `StringBuilder`.
- Let `currentWord` be a copy of the input `word`.
- Loop while `currentWord` is not empty:
  - Get the first character `c = currentWord.charAt(0)`.
  - Find `count`, the length of the prefix of `currentWord` consisting only of character `c`.
  - Determine the size of the chunk to process: `chunkSize = min(count, 9)`.
  - Append `chunkSize` and `c` to `comp`.
  - Update `currentWord` by creating a new substring that excludes the processed chunk: `currentWord = currentWord.substring(chunkSize)`.
- Return the string representation of `comp`.

## Single Pass Iteration
An optimal approach is to iterate through the string just once using a pointer. We can use this pointer to keep track of our current position. In each step, we count the number of consecutive identical characters, up to a maximum of 9, forming a chunk. We then append the count and the character to our result and advance the pointer. This avoids expensive string manipulations and multiple passes.
**Time:** O(N), where N is the length of `word`. The pointer `i` traverses the string from left to right exactly once. Each character is visited a constant number of times, and `StringBuilder.append` operations are amortized O(1). · **Space:** O(N), where N is the length of the input string. This space is used for the `StringBuilder` to construct the output string. In the worst case (e.g., 'abcde'), the output ('1a1b1c1d1e') can be twice the length of the input.
**Pros:** Optimal time complexity of O(N).; Space-efficient as it avoids creating intermediate strings, using a StringBuilder for efficient appends.; Simple and concise implementation through a single pass.
**Cons:** This approach is optimal for the given constraints, so it has no significant disadvantages.
### Explanation
This method processes the string from left to right in a single pass, building the compressed string as it goes. It's efficient because it avoids creating intermediate substrings and re-scanning parts of the string. The core idea is to use a single pointer `i` that always moves forward, consuming characters as it forms compressed chunks.

```java
class Solution {
    public String compressedString(String word) {
        StringBuilder comp = new StringBuilder();
        int i = 0;
        int n = word.length();
        while (i < n) {
            char c = word.charAt(i);
            int count = 0;
            // Count consecutive occurrences of character c, up to 9
            while (i < n && word.charAt(i) == c && count < 9) {
                count++;
                i++;
            }
            comp.append(count);
            comp.append(c);
        }
        return comp.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` called `comp`.
- Initialize a pointer `i = 0` to traverse the input `word`.
- Loop while `i` is less than the length of `word`:
  - Store the character at the current position: `char c = word.charAt(i)`.
  - Initialize a `count = 0` for the current chunk.
  - Start a nested `while` loop that continues as long as `i` is within bounds, the character at `i` is `c`, and `count` is less than 9.
  - Inside the nested loop, increment `count` and `i`.
  - After the nested loop, append the final `count` and the character `c` to `comp`.
- After the main loop finishes, return `comp.toString()`.

# Solutions
### Java

```java
class Solution {
public
  String compressedString(String word) {
    StringBuilder ans = new StringBuilder();
    int n = word.length();
    for (int i = 0; i < n;) {
      int j = i + 1;
      while (j < n && word.charAt(j) == word.charAt(i)) {
        ++j;
      }
      int k = j - i;
      while (k > 0) {
        int x = Math.min(9, k);
        ans.append(x).append(word.charAt(i));
        k -= x;
      }
      i = j;
    }
    return ans.toString();
  }
}

```

### JavaScript

```javascript
/** * @param {string} word * @return {string} */ var compressedString = function ( word ) { const ans = []; const n = word . length ; for ( let i = 0 ; i < n ; ) { let j = i + 1 ; while ( j < n && word [ j ] === word [ i ]) { ++ j ; } let k = j - i ; while ( k ) { const x = Math . min ( k , 9 ); ans . push ( x + word [ i ]); k -= x ; } i = j ; } return ans . join ( '' ); };
```

### CPP

```cpp
class Solution {
public:
  string compressedString(string word) {
    string ans;
    int n = word.length();
    for (int i = 0; i < n;) {
      int j = i + 1;
      while (j < n && word[j] == word[i]) {
        ++j;
      }
      int k = j - i;
      while (k > 0) {
        int x = min(9, k);
        ans.push_back('0' + x);
        ans.push_back(word[i]);
        k -= x;
      }
      i = j;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def compressedString(self, word: str) -> str: g = groupby(word) ans = [] for c, v in g: k = len(list(v)) while k: x = min(9, k) ans . append(str(x) + c) k -= x return "" . join(ans)

```