# The Long Run

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

Canonical URL: <https://datadriven.io/problems/the_long_run>

Domain: Python · Difficulty: easy · Seniority: L4 · Asked in: Amazon

## Problem

We're shrinking repetitive log lines before they land in cold storage. Collapse each stretch of the same character in a row into that character followed by how many times it repeats there, and return the compacted string.

## 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**

```python
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
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the string length, one pass.
> 
> Space: O(n) for the result string in the worst case, when every character differs and nothing compresses.

**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 Pitfall**
>
> Forgetting the final `result += current + str(count)` after the loop. The last character group is never emitted inside the loop because there is no subsequent character change to trigger it, so the encoding comes back one run short.

> **Interviewers Watch For**
>
> Whether the candidate flushes the final run without being prompted, and whether they notice that a per-character count (not a global one) is what keeps non-adjacent duplicates separate.

---

## Common follow-up questions

- How would you implement the decoder? _(Tests parsing character-count pairs and expanding each character by its count.)_
- What if counts should be omitted when they equal 1? _(Tests adding a conditional: only append the count if it exceeds 1.)_
- What if the input can itself contain digits? _(Tests that the encoding becomes ambiguous unless you add a delimiter or escape sequence.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_long_run)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.