Longest unique window: move the boundary forward

Constructed practice problem; no company attribution. Prerequisites: maps and window basics.

Candidate brief

THE PROBLEM

A text inspection tool highlights the longest contiguous run with no repeated code point. Return positions so the interface can highlight the original string. When two runs are equally long, choose the leftmost. How would you trace “abba”?

Write this:

def longest_unique_window(text):
    ...

Contract	Decision
Input	Python string, exact code points
Output	Half-open `(start, end)` indices; `text[start:end]` is longest unique run
Boundaries	Empty string gives `(0, 0)`; ties choose smallest start
Invalid input	Non-string raises `ValueError`
Excluded	Grapheme indexing, normalization, and noncontiguous subsequences

Optional refresher · the underlying tool

A window is a contiguous slice text[left:right+1]. Keep the left boundary from moving backward when a repeated character was seen outside the current window:

last_seen = {"a": 0}
left = 2
left = max(left, last_seen.get("a", -1) + 1)
print(left)  # 2, not 1

For "abba" the longest answer is "ab" or "ba", length 2. Trace all four steps before coding.

A design choice worth saying aloud

last_seen deliberately overwrites an index whenever a character recurs; the latest position is the one needed to move the window. left may move right but never left. Trace abba: at the final a, its old index is outside the active window, so shrinking backward would manufacture an invalid answer.

What the interviewer expects

The interviewer gives you the scenario and the contract above. Explain what a successful call returns, walk through one example below, and name what your state means before choosing a data structure.

Done means: Half-open (start, end) indices; text[start:end] is longest unique run.

Now predict each output before looking at the reference; invalid input should leave any existing state unchanged unless the contract says otherwise.

Test-case scenarios to settle before coding

01 · Representative

Input / starting state: "abba"
Expected result: (0, 2) for "ab"

What it is testing: The left edge never moves backward.

02 · Empty

Input / starting state: ""
Expected result: (0, 0)

What it is testing: Half-open indices still form a valid empty slice.

03 · All repeated

Input / starting state: "aaaa"
Expected result: (0, 1)

What it is testing: A repeated character closes the longer window.

04 · Tie

Input / starting state: "abba"
Expected result: (0,2) for "ab", before tied "ba"

What it is testing: Equal lengths do not replace the earlier answer.

05 · Exact code points

Input / starting state: "aA"
Expected result: (0, 2)

What it is testing: Case-sensitive symbols are distinct.

06 · Invalid

Input / starting state: non-string input
Expected result: ValueError

What it is testing: The API does not coerce collections to text.

For each case, show which branch or state change produces that result.

longest_unique_window("abba") == (0, 2) highlights "ab". longest_unique_window("aaaa") == (0, 1); longest_unique_window("") == (0, 0). longest_unique_window(["a"]) raises ValueError.

Before opening the explanation, restate the contract, trace the smallest useful example, implement a baseline, and identify the repeated work. Then implement your improvement independently and derive tests from the contract. Say what your state means before saying which data structure stores it.

Worked lesson, changed requirements, and reference

Discover why discarded starts stay discarded

A contiguous window is a slice with no skipped positions. A baseline starts at each position, adds characters to a set, and stops at its first duplicate. It is correct and O(n²) time in the worst case, with O(k) temporary set space. Adjacent starts redo most of the work. To reuse state, scan the right edge once and store the latest position of every character encountered.

Right / character	Previous position	Left before → after	Current slice	Best
0 / a	none	0 → 0	a	`[0, 1)`
1 / b	none	0 → 0	ab	`[0, 2)`
2 / b	1	0 → 2	b	`[0, 2)`
3 / a	0	2 → 2	ba	`[0, 2)`

Before adding a character, the current window is unique and last[c] stores its latest occurrence anywhere in the scanned prefix. If that occurrence is inside the current window, move left just beyond it. Otherwise keep left unchanged: left = max(left, last[c] + 1). The final a above shows why assigning without max is wrong: it would move left backward and reintroduce both bs.

After the update, the window is unique and is the longest valid window ending here. Any earlier start would include the duplicate that forced the boundary; no later right edge can make that earlier start unique again. Comparing this candidate with the best at every right endpoint therefore covers an optimum. Update only for a strictly longer length to retain the earliest tie. Expected time is O(n), auxiliary space O(k) for distinct code points, and output O(1). Returning indices avoids copying every candidate substring, which could hide quadratic allocation behind otherwise linear pointer work.

Follow-up 1: at most two distinct characters

Predict why a last-position jump for the newest duplicate no longer works. Repeated copies are legal now; the violation is a third distinct character. Maintain frequencies and shrink until at most two counts remain positive.

Read from `eceba`	Counts before shrinking	Required shrink	Valid window
e, c, e	`{e: 2, c: 1}`	none	ece
b	`{e: 2, c: 1, b: 1}`	remove e, then c	eb
a	`{e: 1, b: 1, a: 1}`	remove e	ba

Each position enters and leaves once, so the nested shrinking loop is O(n) overall. A count reaching zero, not merely a removal, changes distinctness.

Follow-up 2: consume chunks and return the text

Chunk boundaries must not reset the invariant: ab then ba is still abba. If only offsets are required, no text buffer is needed; returning actual text requires retention or replay. A senior candidate proves amortized movement and tests a stale last occurrence. A lead candidate defines offset units, chunk ownership, and a maximum retained text budget before offering streaming output.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/04-longest-unique-window
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

Reference implementation · solution.py

def longest_unique_window(text):
    if not isinstance(text, str):
        raise ValueError("text must be a string")
    left = 0
    last_seen = {}
    best = (0, 0)
    for right, char in enumerate(text):
        left = max(left, last_seen.get(char, -1) + 1)
        last_seen[char] = right
        if right + 1 - left > best[1] - best[0]:
            best = left, right + 1
    return best

Contract and oracle tests · test_solution.py

import itertools
import unittest
from solution import longest_unique_window

class WindowTests(unittest.TestCase):
    def test_boundaries(self):
        self.assertEqual(longest_unique_window("abba"), (0, 2))
        self.assertEqual(longest_unique_window(""), (0, 0))
        self.assertEqual(longest_unique_window("aaaa"), (0, 1))
        self.assertEqual(longest_unique_window("🙂é🙂x"), (1, 4))
        with self.assertRaises(ValueError):
            longest_unique_window([])

    def test_substring_oracle(self):
        for n in range(7):
            for chars in itertools.product("abc", repeat=n):
                text = "".join(chars)
                candidates = [(i, j) for i in range(n + 1) for j in range(i, n + 1)
                              if len(set(text[i:j])) == j - i]
                expected = min(candidates, key=lambda pair: (-(pair[1] - pair[0]), pair[0]))
                self.assertEqual(longest_unique_window(text), expected)

if __name__ == "__main__":
    unittest.main()