Run-Length Compress a Character List With Multi-Digit Counts
Company: Abridge
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
You are given a non-empty list `chars` of single characters. Compress it with run-length encoding: scan the list from left to right and split it into maximal groups of consecutive equal characters. For each group, write the character once, and if the group has more than one character, follow it with the decimal digits of the group's length, each digit as a separate list element.
The classic form of this task compresses in place: the result is written over the beginning of the input list using only constant extra space, and the new length is returned. So that the result can be checked, this version returns the compressed list itself. Aim to write it in a way that could run in place.
### Function Signature
```python
def compress(chars: list[str]) -> list[str]:
```
### Rules
- A group of length 1 is written as just its character, with no `"1"` after it.
- A group length of 10 or more is written as several digit elements; for example, a group of 12 becomes the character followed by `"1"` and `"2"`.
- Groups are formed only from adjacent equal characters. The same character appearing again later starts a new group.
- Characters are compared exactly, so an uppercase letter and its lowercase form are different characters.
- Return the compressed elements in order, as a list of single-character strings.
### Constraints
- `1 <= len(chars) <= 2000`
- Each element is a single character: an English letter, a decimal digit, or a printable ASCII symbol.
### Examples
**Example 1**
```text
Input: chars = ["x", "x", "x", "y", "z", "z"]
Output: ["x", "3", "y", "z", "2"]
```
**Example 2**
```text
Input: chars = ["a", "b", "b", "a", "a"]
Output: ["a", "b", "2", "a", "2"]
```
The two runs of `"a"` are separated by the run of `"b"`, so they are compressed separately.
**Example 3**
```text
Input: chars = ["k", "k", "k", "k", "k", "k", "k", "k", "k", "k", "k", "k"]
Output: ["k", "1", "2"]
```
The single run has length 12, which is written as two digit elements.
Overview: From an Abridge online assessment: run-length compress a list of characters, writing each run of equal adjacent characters as the character followed by its length, with lengths of 10 or more split into separate digit characters. It tests careful run handling and the in-place, constant-space form of the problem.
You are given a non-empty list `chars` of single characters. Compress it with run-length encoding: scan the list from left to right and split it into maximal groups of consecutive equal characters. For each group, write the character once, and if the group has more than one character, follow it with the decimal digits of the group's length, each digit as a separate list element.
The classic form of this task compresses in place: the result is written over the beginning of the input list using only constant extra space, and the new length is returned. So that the result can be checked, this version returns the compressed list itself. Aim to write it in a way that could run in place.
Implement `compress(chars)` and return the compressed list.
### Rules
- A group of length 1 is written as just its character, with no `"1"` after it.
- A group length of 10 or more is written as several digit elements, in the order the digits appear in the decimal number; for example, a group of 12 becomes the character followed by `"1"` and `"2"`.
- Groups are formed only from adjacent equal characters. The same character appearing again later starts a new group.
- Characters are compared exactly, so an uppercase letter and its lowercase form are different characters.
- Return the compressed elements in order, as a list of single-character strings.
### Constraints
- `1 <= len(chars) <= 2000`
- Each element is a single character: an English letter, a decimal digit, or a printable ASCII symbol.
Every group length is at most 2000, so no value exceeds 2^31 - 1 and a 32-bit integer holds any count.
### Examples
**Example 1**
```text
Input: chars = ["x", "x", "x", "y", "z", "z"]
Output: ["x", "3", "y", "z", "2"]
```
The groups are three `"x"`, one `"y"` and two `"z"`; the single `"y"` is written without a count.
**Example 2**
```text
Input: chars = ["a", "b", "b", "a", "a"]
Output: ["a", "b", "2", "a", "2"]
```
The two runs of `"a"` are separated by the run of `"b"`, so they are compressed separately.
Constraints
- 1 <= len(chars) <= 2000
- Each element is a single character: an English letter, a decimal digit, or a printable ASCII symbol.
Examples
Input: (['x', 'x', 'x', 'y', 'z', 'z'],)
Expected Output: ['x', '3', 'y', 'z', '2']
Explanation: Source example 1: groups xxx, y and zz; the single y gets no count.
Input: (['a', 'b', 'b', 'a', 'a'],)
Expected Output: ['a', 'b', '2', 'a', '2']
Explanation: Source example 2: the two runs of a are separated by b, so they are compressed separately.
Hints
- A group ends exactly where the next element differs from the group's character, or where the list ends.
- A group's length contributes one element per decimal digit, and a length of 1 contributes nothing.
- Input elements such as "1" are ordinary characters; they are only compared with their neighbours.