Sliding Window Technique Explained With Simple Examples

// O(n) variable window: expand right, shrink left when duplicate found
function lengthOfLongestSubstring(s) {
  const charSet = new Set();  // tracks characters currently in window
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    // Shrink window from left until the character at 'right' is no longer a duplicate
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);  // remove leftmost character
      left++;                   // shrink window from left
    }

    charSet.add(s[right]);                         // add new right character
    maxLen = Math.max(maxLen, right - left + 1);   // update max window size
  }

  return maxLen;
}

// Example walkthrough: "abcabcbb"
// right=0: add 'a' → window=["a"], maxLen=1
// right=1: add 'b' → window=["a","b"], maxLen=2
// right=2: add 'c' → window=["a","b","c"], maxLen=3
// right=3: 'a' is in set → remove 'a', left=1 → window=["b","c"] → add 'a', maxLen=3
// right=4: 'b' is in set → remove 'b', left=2 → window=["c","a"] → add 'b', maxLen=3
// ... continues, max stays 3
// Result: 3 ("abc")

lengthOfLongestSubstring("abcabcbb"); // → 3
lengthOfLongestSubstring("pwwkew");   // → 3 ("wke")
lengthOfLongestSubstring("bbbbb");    // → 1

// O(n) — expand right until all chars found, then shrink left as much as possible
function minWindow(s, t) {
  // Count required characters from target t
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;

  let have = 0;                         // characters in window matching need count
  const required = Object.keys(need).length;  // distinct chars needed
  const window = {};                    // current window character counts
  let minLen = Infinity;
  let res = '';
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    // Expand: add s[right] to window
    const c = s[right];
    window[c] = (window[c] || 0) + 1;
    if (need[c] && window[c] === need[c]) have++;  // satisfied one more requirement

    // Shrink from left while all requirements are satisfied
    while (have === required) {
      // Update result if current window is smaller
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        res = s.slice(left, right + 1);
      }
      // Remove s[left] from window and slide left pointer
      window[s[left]]--;
      if (need[s[left]] && window[s[left]] < need[s[left]]) have--;
      left++;
    }
  }

  return res;
}

minWindow("ADOBECODEBANC", "ABC"); // → "BANC"
minWindow("a", "a");               // → "a"
minWindow("a", "aa");              // → "" (impossible)

// ─── Template: Variable-size sliding window ──────────────────────────────────
function slidingWindowTemplate(arr) {
  let left = 0;

  // Window state — customize based on problem:
  let windowSum = 0;       // for sum-based problems
  // let windowCount = {};  // for frequency-based problems
  // let windowSet = new Set(); // for uniqueness problems

  let result = 0;  // or -Infinity, Infinity, '' depending on problem

  for (let right = 0; right < arr.length; right++) {
    // STEP 1: Expand window — add arr[right]
    windowSum += arr[right];  // or windowCount[arr[right]]++ etc.

    // STEP 2: Shrink window while constraint is violated
    while (/* window is invalid — customize condition */) {
      // Remove arr[left] from window state
      windowSum -= arr[left];  // or windowCount[arr[left]]-- etc.
      left++;  // shrink from left
    }

    // STEP 3: Update result (window is now valid)
    result = Math.max(result, right - left + 1);  // or windowSum, count, etc.
  }

  return result;
}

// ─── Template: Fixed-size window of size k ────────────────────────────────────
function fixedSlidingWindow(arr, k) {
  // Build first window
  let windowState = /* sum, map, set of arr[0..k-1] */;

  // Initial result from first window
  let result = /* process first window */;

  for (let right = k; right < arr.length; right++) {
    // Add new right element
    // windowState += arr[right];  or add arr[right] to map/set

    // Remove leftmost element (always arr[right - k] for fixed window)
    // windowState -= arr[right - k];  or remove arr[right - k] from map/set

    // Update result
    // result = Math.max(result, windowState);
  }

  return result;
}