DP -> Sliding Window And Window DP

Problems where a moving window carries state, costs, or feasibility information that updates incrementally.

• Topic slug: dp/sliding-window
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 2
• Repo companion pages: 2
• Curated external problems: 16

Microtopics

• window-cost
• monotone-window
• two-multiset-maintenance
• amortized-updates
• window-dp-state
• nested-intervals

Learning Sources

Source	Type
USACO Guide two pointers	Reference
Competitive Programmer's Handbook	Reference

Practice Sources

Source	Type
CSES Problem Set	Practice
Codeforces two-pointers tag	Practice

Repo Companion Material

Material	Type
DP cheatsheet	quick reference
Data structures cheatsheet	adjacent reference

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dice Combinations	CSES	Easy	-	-	-	1D DP; Window Size 6	bounded-width transition window
Array Description	CSES	Medium	-	-	-	Bounded Transition DP; Prefix Sums	local-value window on adjacent states
Candies	AtCoder DP Contest	Medium-Hard	-	-	-	Prefix-Sum DP; Bounded Range	windowed transitions via prefix sums

At Most K Distinct

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Fruit Into Baskets	LeetCode	Medium	Frequency-Window	Two-Pointers	Hash Maps; Window Invariants	Distinct-Count; Two-Pointers	A classic at-most-two-distinct window that teaches how to expand and shrink correctly.

Distinct Count Window

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sliding Window Distinct Values	CSES	Easy	Frequency-Window	Two-Pointers; Hash-Map	Hash Maps; Two Pointers	Frequency-Map; Distinct	A clean frequency-based window problem that teaches how to maintain a moving constraint.

Fixed Length Frequency Match

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Permutation in String	LeetCode	Easy	Frequency-Window	Two-Pointers	Frequency Arrays; Strings	Anagram; Frequency-Array	A crisp fixed-window frequency problem that is perfect for learning sliding updates.

Median Cost

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sliding Window Cost	CSES	Medium	Order-Statistics	Balanced-Multiset	Sliding Window Median; Prefix Sums	Median; Cost	A natural companion to median maintenance that adds aggregate cost tracking.

Median Maintenance

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sliding Window Median	CSES	Medium	Order-Statistics	Balanced-Multiset	Multisets; Heap Balancing	Median; Multiset	A classic sliding-window problem that upgrades basic window maintenance to order statistics.

Minimum Covering Window

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Minimum Window Substring	LeetCode	Hard	Frequency-Window	Two-Pointers; Hash-Map	Hash Maps; Substring Counting	Substring; Frequency-Map	The classic minimum-cover window that shows how to shrink only after a valid window is found.

Monotonic Minimum

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sliding Window Minimum	CSES	Easy	Window-Maintenance	Deque	Queues; Amortized Analysis	Deque; Minimum	The standard monotonic-deque template for maintaining a window minimum in O(n).

Product Constraint

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Subarray Product Less Than K	LeetCode	Medium	Product-Window	Two-Pointers	Multiplication Invariants; Arrays	Multiplicative; Two-Pointers	A canonical positive-array sliding window where the product constraint controls window growth.

Single Character Dominance

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Longest Repeating Character Replacement	LeetCode	Medium	Frequency-Window	Two-Pointers	Frequency Counting; Window Invariants	Frequency; Replacement	A very common window problem where a simple count invariant unlocks the maximum length.

Unique Character Window

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Longest Substring Without Repeating Characters	LeetCode	Medium	Two-Pointers	Two-Pointers	Hash Maps; Strings	Hash-Map; Substring	The most recognizable variable-length window problem for maintaining a uniqueness invariant.

Unique Sum Window

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Maximum Erasure Value	LeetCode	Medium	Frequency-Window	Two-Pointers	Hash Maps; Prefix Sums	Unique-Window; Prefix-Sums	A good combination of uniqueness maintenance and rolling aggregate sums.

Window Inversion Count

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sliding Window Inversions	CSES	Hard	Inversion-Counting	Fenwick-Tree	Coordinate Compression; Order Statistics	Inversions; Fenwick	A strong advanced window problem that combines local maintenance with inversion counting.

Windowed Histogram

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sliding Window Advertisement	CSES	Medium	Monotonic-Window	Deque; Prefix-Scan	Monotonic Queue; Prefix Sums	Deque; Max-Area	A nice windowed maximization problem where subarray-maintenance meets a geometric interpretation.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
SLIDINGWINDOWMINIMUM	Sliding Window Minimum	primary	medium	-	Note	Code
TFIELD	Ruộng bậc thang	primary	hard	nested polygons; weighted sliding window; shoelace preprocessing	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py