Katkat
Back

Compress a String by Run-Length Counts, Keeping the Original When Not Shorter

New RelicBackend Engineer · Onsite
MediumBackend EngineerOnsiteCoding & Algorithms

Last updated

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.

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

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

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

Input: s = "aabb"
Output: "aabb"

The compressed form a2b2 has 4 characters, the same as the original, so the original is returned.

Example 3

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.