Compress a String by Run-Length Counts, Keeping the Original When Not Shorter
Company: New Relic
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement basic string compression based on runs of repeated characters. Replace every maximal run of consecutive identical characters with that character followed by the length of the run, written in decimal. For example, `aabcccccaaa` becomes `a2b1c5a3`.
If the compressed string is not strictly shorter than the original string, return the original string unchanged.
In the interview you are also expected to state the time and space complexity of your implementation, walk through the edge cases it handles, and discuss how the code could be optimized.
### Function Signature
```python
def compress(s: str) -> str:
```
### Rules
- A run is a maximal block of consecutive equal characters. Every run is encoded, including runs of length 1 (a single `b` becomes `b1`).
- Matching is case-sensitive: `a` and `A` are different characters, so `aA` consists of two runs.
- A run longer than 9 is written with all of its digits: a run of twelve `a` characters becomes `a12`.
- Compare lengths only after compressing the whole string. Return the compressed string if its length is strictly less than `len(s)`; if it is equal or longer, return `s`.
- The empty string is returned as the empty string.
### Constraints
- `0 <= len(s) <= 10^5`
- `s` contains only English letters, `a` to `z` and `A` to `Z`.
### Examples
**Example 1**
```text
Input: s = "aabcccccaaa"
Output: "a2b1c5a3"
```
The runs are `aa`, `b`, `ccccc` and `aaa`. The compressed form has 8 characters, fewer than the original 11.
**Example 2**
```text
Input: s = "aabb"
Output: "aabb"
```
The compressed form `a2b2` has 4 characters, the same as the original, so the original is returned.
**Example 3**
```text
Input: s = "aaaaaaaaaaB"
Output: "a10B1"
```
The input is ten `a` characters followed by one `B`. The run of ten is written as `a10`, and the compressed form has 5 characters, fewer than the original 11.
Overview: Implement run-length string compression that replaces each run of repeated characters with the character and its count, returning the original string when the compressed form is not strictly shorter. Tests careful run handling, multi-digit counts, the tie rule, and complexity and edge-case discussion.
Read the full New Relic Backend Engineer interview experience this question came from
Given a string `s`, compress it using runs of repeated characters: replace every maximal run of consecutive identical characters with that character followed by the length of the run, written in decimal. For example, `aabcccccaaa` becomes `a2b1c5a3`.
If the compressed string is not strictly shorter than `s`, return `s` unchanged; otherwise return the compressed string.
**Rules**
- A run is a maximal block of consecutive equal characters. Every run is encoded, including runs of length 1 (a single `b` becomes `b1`).
- Matching is case-sensitive: `a` and `A` are different characters, so `aA` consists of two runs.
- A run longer than 9 is written with all of its digits: a run of twelve `a` characters becomes `a12`.
- Compare lengths only after compressing the whole string. Return the compressed string if its length is strictly less than `len(s)`; if it is equal or longer, return `s`.
- The empty string is returned as the empty string.
**Example 1**
```text
Input: s = "aabcccccaaa"
Output: "a2b1c5a3"
```
The runs are `aa`, `b`, `ccccc` and `aaa`. The compressed form has 8 characters, fewer than the original 11.
**Example 2**
```text
Input: s = "aabb"
Output: "aabb"
```
The compressed form `a2b2` has 4 characters, the same as the original, so the original is returned.
**Constraints**
- `0 <= len(s) <= 10^5`
- `s` contains only English letters, `a` to `z` and `A` to `Z`.
Every run length and string length is at most 10^5, so no value exceeds 2^31 - 1 and a 32-bit `int` is enough in every language.
Constraints
- 0 <= len(s) <= 10^5
- s contains only English letters, 'a' to 'z' and 'A' to 'Z'.
Examples
Input: ('',)
Expected Output: ''
Explanation: Empty string: the empty compression is not shorter, so the empty string is returned.
Input: ('a',)
Expected Output: 'a'
Explanation: Single character: a1 is longer than a, so the original is returned.
Hints
- A run ends where the next character differs from the current one or where the string ends; make sure the last run is written out too.
- Run lengths of 10 or more need every decimal digit, and 'a' and 'A' never belong to the same run.
- Build the whole compressed string before comparing lengths, and remember that an equal length keeps the original.