Middle · Algorithms

Sliding window without repeated scans

Find the longest byte substring with no repeated byte.

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

ALGORITHM LAB · STEP THROUGH THE INVARIANT

Input scenario

abba

STEP 1 / 5

Unique-byte window

Input

These presets are ASCII; indexes count bytes.

Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

func UniqueBytes(s string) int {
	last := make(map[byte]int)
	left, best := 0, 0
	for right := 0; right < len(s); right++ {
		if p, ok := last[s[right]]; ok && p >= left {
			left = p + 1
		}
		last[s[right]] = right
		if right-left+1 > best {
			best = right - left + 1
		}
	}
	return best
}

Reveal a strong answer

Maintain a window [left,right] containing unique bytes and a map of last positions. On a repeated byte, move left to max(left,last+1); never move left backward.
Each index enters and leaves the logical window at most once, so repeated characters do not require rescanning the window. Keep the best length and its start if the substring itself is needed.
The unit matters. This version operates on bytes and suits ASCII keys or byte protocols. A rune version needs rune positions or carefully tracked byte offsets; grapheme-aware text needs a different contract.

Common trap

Assigning left = last+1 without max breaks on abba by moving the boundary backward.

Complexity & use

O(n) time, O(min(n,256)) storage for bytes. Useful for bounded stream/window reasoning.

Try it

Trace "abba" and explain why the answer is2, then define what changes for emoji.

Worked solution

At the second b, left becomes2. The final a was last seen at0, outside the current window, so left stays2 and best remains2. For Unicode, first state whether uniqueness means code points or grapheme clusters.

Change the constraint

What changes for a longest window that contains at most k distinct values?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-20. Use documentation for your pinned runtime, driver and tool version.