The Window Cleaner

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

Domain
Python
Difficulty
medium
Seniority
L4

Problem

Each user session is captured as one string of single-character event codes, with s holding the codes for one replay. Find the length of the longest stretch within s where no event code appears twice.

Keep it fresh, keep it unique.

Example 1

Input:

s = "abcabcbb"

Output:

3

Example 2

Input:

s = "pwwkew"

Output:

3

Worked solution and explanation

What this really is

This is a sliding window hiding inside a string problem. The skill being probed: can you grow a clean window from the right and trim it from the left so that every character inside it stays unique, without ever rescanning what you already cleared? Almost everyone reaches for nested loops that re-check every substring, and it passes the two visible tests fine. Then the input gets long and that O(n^2) (or O(n^3)) instinct times out. The trap is recomputation: the moment you re-scan the window after each move, you have lost.

How to get there

Step 1: Pull the new code into the window

Step right forward over each character and add it to the tracking set. This is the only place the window grows.

Step 2: Trim from the left until the window is clean

If the incoming code is already in the set, walk left forward, removing s[left] each time, until the duplicate has been evicted. You never look backward past left again.

Step 3: Track the widest clean window

After the window is clean, its size is right - left + 1. Keep the running best. The answer is the largest clean window you ever held.

The solution

Sliding window with set-based duplicate detection
def longest_unique_substr(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

Common follow-up questions