The String Shrinker

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4
Asked in
Amazon

Problem

A storage layer keeps text compact by collapsing repeated characters: given a string s, return its run-length encoding, where each run becomes the character followed by its length, and a lone character keeps just itself. If the encoded form would not be shorter than s, return s unchanged.

Compress the string. Shorter wins.

Example 1

Input:

s = "aabcccccaaa"

Output:

"a2bc5a3"

Example 2

Input:

s = "abcdef"

Output:

"abcdef"

Worked solution and explanation

What this problem really is

This is run-length encoding with a count-1 omission bolted on. Anyone writes the basic loop that counts a run and emits character-plus-count. The separator is two rules that live at the edges: a run of a single character emits just the character (no '1'), and if the encoded string does not come out strictly shorter, you hand back the original untouched. Get the length check wrong (using <= instead of <, or forgetting it) and you ship 'a2b2' in place of 'aabb', a compressor that made nothing smaller.

Break down the requirements

Step 1: Track character runs

Walk the string once, keeping the character you are inside of and how many of it you have seen in a row. When the character changes, that run is done.

Step 2: Emit the count only when it earns its place

Flush a run by appending the character, then the count only when it exceeds 1. This is the rule that keeps single characters bare, so 'abc' never becomes 'a1b1c1'.

Step 3: Return the shorter of original or compressed

After building the encoded string, compare lengths. Return the encoded form only if it is strictly shorter than the input; otherwise return the input. Equal length loses.

The solution

Run-length encoding with count-1 omission
def compress(s: str) -> str:
    if not s:
        return s
    parts = []
    current = s[0]
    count = 1
    for ch in s[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(current)
            if count > 1:
                parts.append(str(count))
            current = ch
            count = 1
    parts.append(current)
    if count > 1:
        parts.append(str(count))
    compressed = "".join(parts)
    return compressed if len(compressed) < len(s) else s

One pass, a parts list joined at the end, and a strict-less-than gate on the length.

Common follow-up questions