A segment, not a selection

Positive costs [3,1,2,5,1], target 7.

Find the shortest contiguous qualifying segment.

What does enumerating every start and end repeat?

1 / 10

When may a start be retired?

At right=3: sum 11, length 4.

Remove 3: sum 8, length 3.

Remove 1: sum 7, length 2.

Why never revisit those discarded starts?

2 / 10

Trace: target 7

At the last element of [2,3,1,2,4,3]:

[2,4,3] sum 9 → length 3

[4,3] sum 7 → length 2

[3] sum 3 → stop

3 / 10

Trace: abba

Left boundaries: 0,0,2,2.

At the last a, its previous index 0 is already outside the window.

Why is assigning left=1 wrong?

4 / 10

Counts are not sets

Target AAC; candidate AC.

Distinct letters agree. Multiplicities do not.

When should formed decrease as an A leaves?

5 / 10

Empty is a defined case

Empty pattern:

CheckInclusion → true

FindAnagrams → all boundaries

MinWindow → empty result

6 / 10

Historical max is not current max

AABABBA, k=1 → best length 4.

A retained window may need more than one replacement after maxFreq becomes stale.

The proof concerns when the best length can grow.

7 / 10

Offsets expose hidden matches

Text xbarfoo, words [bar,foo]

Word length 3; valid start 1.

Run offsets 0,1,2, not only offset 0.

8 / 10

The cost inside the update

N text bytes, L-byte words.

O(N) token-map operations across offsets do not imply O(N) byte work when L varies.

Hashing a token can inspect L bytes.

9 / 10

Reconstruct without a template

Choose state, entering update, leaving update, validity direction, and recording moment.

Then name the condition that lets left move only forward.

10 / 10