The Long Run

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

Log lines headed for cold storage are full of repeated characters. Each line arrives as a string s of lowercase letters, read left to right. A stretch of the same character in a row is stored as that character followed by how many times it repeats in that stretch. Return the compacted version of s.

Say it once, then say how many times it kept saying it.

Example 1

Input:

s = "wwwwaaadexxxxxx"

Output:

"w4a3d1e1x6"

Example 2

Input:

s = "abc"

Output:

"a1b1c1"

Worked solution and explanation

What this problem really is

This is consecutive-run grouping wearing a compression costume. The instinct is to reach for a Counter or a frequency dict, and it will happily pass 'abc' and even 'aaa'. It dies on 'aabba': a tally merges the two 'a' groups into one and you emit 'a3b2' for a string that must encode as 'a2b2a1'. The actual skill is carrying state across an ordered scan (which character am I inside, how long has it run) and emitting at every boundary. The second killer is the boundary that never fires: the last run has no character-change after it, so if you only emit on a change, the final group silently vanishes.

Break down the requirements

Step 1: Track the current character and its run count

Seed with the first character and a count of 1. This is a per-run count, not a global tally, which is exactly why a Counter cannot stand in for it.

Step 2: When the character changes, emit the run

When the next character differs, append the current character and its count to the result, then reset the tracker to the new character with count 1.

Step 3: Emit the final run after the loop

The last group is never followed by a character change, so nothing inside the loop emits it. Flush it once, after the loop ends. This single line is where most implementations bleed the final run.

The solution

Single-pass run tracking with count emission
def run_length_encoding(s: str):
    if not s:
        return ''
    result = ''
    current = s[0]
    count = 1
    for i in range(1, len(s)):
        if s[i] == current:
            count += 1
        else:
            result += current + str(count)
            current = s[i]
            count = 1
    result += current + str(count)
    return result
Frequency tally (wrong)
Counting occurrences with a Counter loses adjacency. 'aabba' becomes {a: 3, b: 2}, so you can only produce 'a3b2'. The two separate runs of 'a' are gone.
Ordered scan (correct)
Walking left to right and resetting the count at each boundary preserves adjacency. 'aabba' yields a2, then b2, then a1, exactly 'a2b2a1'.

Common follow-up questions