String compression: run-length encode a character list in place

Given a non-empty list of single characters, compress it with run-length encoding. Split the list into maximal runs of equal adjacent characters. For each run, write the character, then, if the run is longer than one, the digits of its length, each digit as its own element. The classic form does this in place with constant extra space and returns the new length; here return the compressed list, but write it so it could run in place.

Interface

Unless you agree on a different interface with the interviewer, assume:

• compress(chars: list[str]) -> list[str] — the compressed elements in order.

Example

compress(["x", "x", "x", "y", "z", "z"])  ->  ["x", "3", "y", "z", "2"]   # a single "y" gets no count
compress(["a", "b", "b", "a", "a"])       ->  ["a", "b", "2", "a", "2"]   # the two runs of "a" stay separate
compress(["k"] * 12)                      ->  ["k", "1", "2"]
compress(["a"])                           ->  ["a"]

Constraints

• 1 <= len(chars) <= 2000.
• Elements are letters, digits or printable ASCII symbols, compared exactly ("A" and "a" differ). A digit in the input is an ordinary character.

Clarifying questions

• Return the list, or overwrite the input and return the new length?
• Is a run of one written with a "1"? (No.)
• Can the input contain digit characters, and does that make the output ambiguous?
• Is case significant?

What a strong answer covers

• Two pointers: a read pointer that finds the end of each run and a write pointer that writes the character and the count's digits. O(n) time, O(1) extra space in place.
• Why in-place is safe: the compressed form of a run is never longer than the run, so the write pointer never passes the read pointer.
• Multi-digit counts written in order (str(count), or digits pushed in reverse and flipped).
• Edge cases: one element, all equal, all different, runs of exactly 10 and 100.

Follow-ups

• Write the decompressor. What breaks when the input itself can contain digits?
• Compress a stream that arrives in chunks, where a run can span chunks.
• Only compress when it makes the output shorter overall.