Maintain a contiguous range and move its edges instead of re-scanning.
The tell: The words 'contiguous', 'substring', 'subarray', combined with longest/shortest/at most k.
Reach for it when
Longest substring without repeating characters
Minimum window containing all of a target set
Maximum sum of a fixed-size window
At most / exactly k distinct elements
Reference implementation
longest_unique — variable-size window
def longest_unique(s: str) -> int:
last_seen: dict[str, int] = {}
best = start = 0
for i, ch in enumerate(s):
# Only move the left edge forward, never back.
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1
last_seen[ch] = i
best = max(best, i - start + 1)
return best
Complexity: O(n) — each index enters and leaves the window at most once.
What goes wrong
Letting the left edge move backwards — the `>= start` guard is what prevents it.
Using `while` to shrink when the constraint is 'exactly k' — compute atMost(k) - atMost(k-1) instead.
Recomputing the window's sum or counts from scratch, which silently makes it O(n·k).