Variable-size Window

A variable-size window expands and shrinks so that the window always satisfies (or violates) a condition. You typically look for the longest or shortest subarray/substring with a given property.

When to Use

• Keywords like longest, shortest, at most, at least, contains, no more than.
• You can maintain a metric (e.g. count of distinct chars, sum) and adjust the window by moving left when the condition is violated.

Template (Longest Subarray Satisfying Condition)

JavaCopy
int left = 0, best = 0;
for (int right = 0; right < n; right++) {
    // Expand: add nums[right], update state
    while (window violates condition) {
        // Shrink: remove nums[left], update state
        left++;
    }
    // Here window satisfies condition
    best = Math.max(best, right - left + 1);
}
return best;

For shortest subarray, use the same expand/shrink logic but update best = Math.min(best, right - left + 1) when the window satisfies the condition.

Longest Substring Without Repeating Characters

Find the length of the longest substring with all distinct characters.

• Use a window and a frequency map (or set). Expand with right; when a character repeats, shrink left until the duplicate is removed.

JavaCopy
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        count.merge(c, 1, Integer::sum);
        while (count.get(c) > 1) {
            count.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Summary

Variable-size window: expand with right, shrink with left until the condition holds (or fails), and track the longest or shortest valid window. Most substring/subarray problems with “longest” or “shortest” fit this pattern.