Katkat
Back

Run-Length Compress a Character List With Multi-Digit Counts

AbridgeSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

Function Signature

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

Input: chars = ["x", "x", "x", "y", "z", "z"]
Output: ["x", "3", "y", "z", "2"]

Example 2

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

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.