Sliding Window Technique Substring Problems

Fixed-Size Windows

Sliding window algorithms maintain a contiguous range while moving its boundaries. They avoid recomputing each range from scratch by updating a small state when one element enters or leaves.

For a window of size k, compute the first aggregate once, then subtract the outgoing value and add the incoming value. Validate k: it must be positive and no greater than the input length unless the API defines another result. This yields O(n) time instead of O(nk).

Variable-Size Windows

Expand the right boundary to include new data and shrink the left boundary while the validity rule is broken. The method works when the maintained condition changes monotonically enough for left to move only forward. A sum window with negative values often violates that assumption and may need prefix sums instead.

Window State

Maintain exactly what the condition needs: a running sum, character frequency map, distinct count, deque of candidates, or last-seen positions. Update state in the correct order when boundaries move, especially when a frequency falls to zero.

Recognition and Testing

The technique applies to contiguous subarrays or substrings, not arbitrary subsets. Test empty input, k equal to one and full length, repeated values, all-identical input, no valid window, and a valid window at each boundary. State whether the result returns length, indexes, or a copied slice.

Longest Substring Without Repeating Characters

function longestUnique(text) {
        const lastSeen = new Map();
        let left = 0;
        let best = 0;
        for (let right = 0; right < text.length; right++) {
          const previous = lastSeen.get(text[right]);
          if (previous !== undefined && previous >= left) left = previous + 1;
          lastSeen.set(text[right], right);
          best = Math.max(best, right - left + 1);
        }
        return best;
      }

Maximum Fixed-Window Sum

function maxWindowSum(values, k) {
        if (k <= 0 || k > values.length) throw new RangeError('invalid window size');
        let sum = values.slice(0, k).reduce((a, b) => a + b, 0);
        let best = sum;
        for (let right = k; right < values.length; right++) {
          sum += values[right] - values[right - k];
          best = Math.max(best, sum);
        }
        return best;
      }

Before you move on