# The Unbroken Line > The longest stretch that never repeats itself. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L5 ## Problem You're scanning one column of id values pulled from a data export, where each cell is raw text, the ids arrive in the order they were written, and values repeat. The export wrote ids inconsistently, so the same id can show up with extra leading zeros ('7' and '007' are one id), and you read each cell by its numeric value. Return the length of the longest unbroken stretch of the column in which no id appears more than once. ## Worked solution and explanation ### What this problem really is Peel off the data-export wording and this is the longest contiguous no-repeat stretch on an ordered sequence, with one twist up front: the cells are text and the same id can wear extra leading zeros, so '007' and '7' are one id and you parse each cell to its integer value before comparing anything. Almost everyone then produces a number; what separates candidates is refusing two shortcuts. Sorting the ids feels natural, but the answer is defined on arrival order, so a sort returns a wrong length. Counting how many different ids exist is more seductive because it sometimes matches, yet it reports total variety, not the longest unbroken stretch, and overcounts the moment a long unique run is split by an earlier repeat. The real skill: slide one window across the data, keep a live set of the ids inside it, and evict from the left until the incoming id is unique again. Get the eviction boundary wrong and you either report a stretch that still holds a duplicate or collapse back to O(n^2). > **Trick to Solving** > > Parse each cell to an int first so leading-zero twins collapse to one id. Then walk a right pointer across the column, adding each id to a window set. The instant the incoming id is already in the set, the stretch has a repeat, so discard ids[left] and step left forward until the duplicate is gone, then add the new id. The widest window you ever see is the answer, and because every id enters and leaves the set at most once, the whole thing is O(n). --- ### Why the obvious moves fail **Distinct count (one set)** Parse, then drop every id into a set and return its size. On [4, 1, 2, 1, 3, 5] that is five different values, so it answers 5. But the longest unbroken run without a repeat is [2, 1, 3, 5], length 4. The set forgot where the ids sat, so it counted variety instead of a contiguous stretch. Sorting first fails the same way: it discards the order the answer is defined on. **Sliding window (set plus left edge)** Move left to right adding each id to a window set. When an id is already inside, evict from the left until it is gone, then add it, tracking the largest window size. On the same input it correctly reports 4. Each id enters and leaves once, so it is O(n) and it never loses the arrival order. ### Break down the requirements #### Step 1: Read each cell by its numeric value The export wrote the same id in different textual forms, so '007' and '7' are equal only once read as numbers. Convert each cell with int() up front; skip this and the two forms look like distinct ids and inflate the answer. #### Step 2: Add each id to a window set Move a right pointer across the parsed ids, adding each to a set that represents the current stretch. Membership tests are O(1), which is what keeps the pass linear. #### Step 3: Evict from the left on a collision When the incoming id is already in the window, the stretch now has a repeat. Discard ids[left] and advance left, one id at a time, until the duplicate is gone. This is the line people get wrong: move left forward only, never reset it to the start, or an already-evicted id sneaks back in. #### Step 4: Track the widest window After each insert, the current stretch spans right minus left plus one. Keep the maximum across the whole pass; that maximum is the answer, and starting it at 0 means an empty column returns 0 for free. --- ### The solution **Sliding window over a membership set** ```python def longest_distinct_window(id_cells: list[str]) -> int: ids = [int(cell) for cell in id_cells] seen: set[int] = set() left = 0 longest = 0 for right, current in enumerate(ids): while current in seen: seen.discard(ids[left]) left += 1 seen.add(current) window = right - left + 1 if window > longest: longest = window return longest ``` *Parse to int once so leading-zero twins match, then the inner while loop advances left only forward, so the window always holds a distinct set of ids.* > **Time and Space Complexity** > > **Time:** O(n). Parsing is one linear pass; then the right pointer visits each id once and the left pointer only ever moves forward, so across the whole run each id is added and discarded at most once. > > **Space:** O(k) where k is the size of the widest window, bounded by O(n). > **Interviewers Watch For** > > The tell is whether the left edge moves forward only. A candidate who rebuilds the window or resets left on every repeat gives the right number on small inputs but ships O(n^2). The other tell is quietly comparing the raw strings: '7' and '007' then read as different ids, and the distinct-count answer (one set's size) is the trap the interviewer is watching you decline. > **Common Pitfall** > > Answering with the count of distinct ids. It matches on inputs where the whole column is one clean run, then quietly overcounts the first time a long unique stretch is split by an earlier repeat, exactly the [4, 1, 2, 1, 3, 5] case. --- ## Common follow-up questions - What if you also needed to return the actual stretch, not just its length? _(Tests tracking the window's left index and slicing ids[left:right+1] at the moment the maximum updates.)_ - How would this change for a stream you cannot fully store? _(Tests whether the window state is bounded and can advance online rather than needing the full input in memory.)_ - What if a repeat is allowed as long as the two occurrences are more than k apart? _(Tests generalizing the eviction rule from a plain set to a map of counts or last-seen positions.)_ - Could you solve this by sorting first, and why does that break? _(Tests understanding that sorting discards the arrival order the answer depends on, so it cannot be used here.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_unbroken_line) - [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.