The Squeeze

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
L3
Asked in
Amazon

Problem

Given a string, return its run-length encoded form (char followed by run count, e.g. 'aabcccaaa' -> 'a2b1c3a3'). If the encoded form is not strictly shorter than the original, return the original string unchanged.

aaabbb gets old fast. Shrink it.

Example 1

Input:

s = "aabcccaaa"

Output:

"a2b1c3a3"

Example 2

Input:

s = "abc"

Output:

"abc"

Worked solution and explanation

Why this problem exists in real interviews

Strip the compression buzzword away and this is a run-boundary walk with a fallback clause. Anyone can emit char-plus-count while characters keep repeating; two moves separate the people who actually ship it. First, the final run only lives in your accumulator when the loop ends, so if you don't flush it after the loop the last stretch silently disappears. Second, encoding is a bet that can lose: a varied string like 'abc' becomes 'a1b1c1' and grows, so you keep the encoded form only when it is strictly shorter and otherwise hand back the original. Miss either and you return a string that is wrong or longer than what you started with.

Break down the requirements

Step 1: Track the current character and its run length

Seed with the first character and a count of 1. Keep incrementing the count while the next character matches the one you are on.

Step 2: Close a run when the character changes

The moment the character changes, that run is finished: write the character followed by its count, then reset to the new character with a count of 1.

Step 3: Flush the final run, then compare lengths

The loop never sees the end of the last run, so append that final character-count pair explicitly after it. Then keep the encoded string only if it is strictly shorter than the input.

The solution

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

Common follow-up questions