03
Variable Window + Frequency Map (Sliding Window Sub-pattern)
A variable window whose rule depends on counts inside it — how many distinct values, how often the most common letter appears, whether required letters are all present.
Signals in the problem statement
- ›
"at most k distinct"
- ›
"replace at most k characters"
- ›
"contains all characters of t"
- ›
"each character appears at least / at most…"
What makes it different
The state is a count map (array of 26/128 or hash map), plus maybe one extra number such as distinct or maxFreq. Updating it correctly on remove is where bugs live.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Fruit Into BasketsWalkthroughMediumBasic Anchor·LeetCode #904
- 2Longest Substring with K Unique CharactersWalkthroughMediumBasic Reinforcement·GeeksforGeeks
- 3Longest Repeating Character ReplacementWalkthroughMediumSlight Variation·LeetCode #424
- 4Maximize the Confusion of an ExamWalkthroughMediumMedium·LeetCode #2024
- 5Length of Longest Subarray With at Most K FrequencyWalkthroughMediumPattern Transfer·LeetCode #2958
- 6Minimum Window SubstringWalkthroughHardInterview-Level·LeetCode #76
- 7Longest Substring with At Least K Repeating CharactersWalkthroughMediumTricky / Edge Case·LeetCode #395
Template
variable-template.cpp
// Variable window: grow on the right, shrink on the left while invalid.
int longestValidWindow(vector<int>& a) {
int left = 0, best = 0;
// state describing the current window (sum, counts, ...)
for (int right = 0; right < (int)a.size(); right++) {
add(a[right]); // 1. expand: include a[right]
while (!valid()) { // 2. shrink until valid again
remove(a[left]);
left++;
}
best = max(best, right - left + 1); // 3. window [left..right] is valid
}
return best;
}Remember this · Sliding Window
Trigger
Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".
Think
Can I keep a valid range and move it, instead of checking every subarray from scratch?
Key question
When is my current window valid?