Intermediate · Module 7 · Lesson 3
Frequency windows
Track characters or values inside the active range.
15–25 min readLesson 39 of 123
Lesson 39 of 123
1d streakTheory lesson · Step-by-step
Understand Frequency windows
Track characters or values inside the active range.
Worked approach
Trace the reasoning step by step
- 1Add the new right value to the frequency table.
- 2Shrink while counts violate the target condition.
- 3Use distinct, matched, or maximum-frequency counts to evaluate the window.
Concrete example
Find an anagram of "ab" inside "eidbaooo".
- 1Maintain counts for a window of length 2.
- 2At window "ba", counts equal those of "ab".
An anagram starts at index 3.
What must remain true (Loop Invariant)
The frequency table exactly describes characters or values between left and right.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Window traversal
Usually O(n)
O(1) to O(k)
Each boundary moves forward; state size depends on the condition.When to use it
- Contiguous subarrays or substrings with incrementally maintainable state.
- Longest, shortest, count, sum, or frequency constraints.
- Streaming range calculations.
Common mistakes
- Using a variable window when feasibility is not monotonic under shrinking.
- Adding an incoming item but forgetting to remove the outgoing one.
- Updating the answer before the window is valid.
Practice prompts
- Reproduce the worked Frequency windows example without looking at the trace.
- Change one input condition and explain whether the Frequency windows invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.