Stretching a rubber band along a ruler: pull the right end out as far as the rule allows, and when it's too tight, let the left end slide in.
Clues that point here
→ "Longest" or "shortest" substring or subarray with a condition
→ "At most K distinct", "without repeating", "sum at least S"
→ Contiguous range plus a constraint
Not this pattern when
✕ Values can be negative and the condition is on a sum (shrinking no longer helps; use prefix sums + hash map)
✕ The answer isn't contiguous
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Sliding Window: Variable Size · template
Map<Character, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char in = s.charAt(right);
count.merge(in, 1, Integer::sum); // grow: add the new element
while (!valid(count)) { // shrink until the rule holds again
char out = s.charAt(left++);
count.merge(out, -1, Integer::sum);
}
best = Math.max(best, right - left + 1); // longest valid window so far
}
return best;
Common versions
Longest substring without repeating characters
Longest repeating character replacement
Minimum window substring
Minimum size subarray sum
Subarrays with K distinct (at most K minus at most K-1)