Sliding Window ​

Imagine you have the string s = "abcabcbb" and need to find the length of the longest substring with unique characters.

• Brute Force: You start at index 0 (a), check ab, abc, abca (stop- repeating character found). Then move to index 1 (b) and restart the scan. Check bc, bca, bcab (stop). You are constantly re-scanning the same characters, which results in $O(N^2)$ time complexity.
• Sliding Window: You maintain a window [left, right] and a set of characters in the current window.
  • Expand right: [a], [ab], [abc].
  • Next is a. Duplicate found!
  • Instead of restarting, you just slide left forward until the duplicate a is removed. New window: [bc]. Then add the new a: [bca].
  • You never backtrack. You just slide left and right forward. Since each character is visited at most twice (once added by right, once removed by left), the total work is $O(N)$.

The Sliding Window is one of the most powerful techniques in coding interviews. It transforms inefficient brute-force nested loops (checking every single subarray) into a single, elegant linear pass.

If you see a problem asking for the longest, shortest, or target value within a contiguous subarray or substring, you are likely looking at a Sliding Window problem.

How It Works ​

Imagine a physical window frame sliding over a long strip of paper.

1. Expand: You pull the right edge of the frame to see more data.
2. Validate: You check if what you see inside the frame follows the rules.
3. Contract: If you broke a rule (e.g., "too many apples"), you pull the left edge forward until the rule is satisfied again.
4. Record: You note down the size or content of the window whenever it's valid.

This guarantees you visit every right index exactly once and every left index at most once, resulting in $O(N)$ time complexity.

The Template ​

Memorize this structure. It covers 90% of variable-size window problems.

def lengthOfLongestSubstring(s: str) -> int:
    # 1. Window state + pointers
    seen = set()
    left = 0
    best = 0

    # 2. Expand the window (right pointer)
    for right, ch in enumerate(s):
        # 3. Shrink from the left until the window is valid (no duplicates)
        while ch in seen:
            seen.remove(s[left])
            left += 1
        # 4. Add current char and update the answer
        seen.add(ch)
        best = max(best, right - left + 1)

    return best

function lengthOfLongestSubstring(s) {
  // 1. Window state + pointers
  const seen = new Set();
  let left = 0;
  let best = 0;

  // 2. Expand the window (right pointer)
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // 3. Shrink from the left until the window is valid (no duplicates)
    while (seen.has(ch)) {
      seen.delete(s[left]);
      left++;
    }
    // 4. Add current char and update the answer
    seen.add(ch);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

public int lengthOfLongestSubstring(String s) {
    Set<Character> seen = new HashSet<>();
    int left = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        while (seen.contains(ch)) {
            seen.remove(s.charAt(left));
            left++;
        }
        seen.add(ch);
        best = Math.max(best, right - left + 1);
    }

    return best;
}

public int LengthOfLongestSubstring(string s)
{
    var seen = new HashSet<char>();
    int left = 0, best = 0;

    for (int right = 0; right < s.Length; right++)
    {
        char ch = s[right];
        while (seen.Contains(ch))
        {
            seen.Remove(s[left]);
            left++;
        }
        seen.Add(ch);
        best = Math.Max(best, right - left + 1);
    }

    return best;
}

#include <string>
#include <unordered_set>
#include <algorithm>

int lengthOfLongestSubstring(const std::string& s) {
    std::unordered_set<char> seen;
    int left = 0;
    int best = 0;

    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        char ch = s[right];
        while (seen.count(ch)) {
            seen.erase(s[left]);
            ++left;
        }
        seen.insert(ch);
        best = std::max(best, right - left + 1);
    }

    return best;
}

func lengthOfLongestSubstring(_ s: String) -> Int {
    var seen = Set<Character>()
    let chars = Array(s)
    var left = 0
    var best = 0

    for right in 0..<chars.count {
        let ch = chars[right]
        while seen.contains(ch) {
            seen.remove(chars[left])
            left += 1
        }
        seen.insert(ch)
        best = max(best, right - left + 1)
    }

    return best
}

Key Signals ​

You can save valuable minutes in an interview by recognizing these signals immediately:

Common Pitfalls ​

Even with the template, candidates often trip up on these details:

1. The "While" vs. "If" ​

When the window becomes invalid, you must shrink it until it is valid again. This almost always requires a while loop, not a simple if statement.

• Bad: if window_sum > target: left += 1
• Good: while window_sum > target: left += 1

2. Wrong Update Timing ​

• For "Longest" problems: Update the answer after the while loop (when the window is guaranteed valid).
• For "Shortest" problems: Update the answer inside the while loop (while the window is valid, before shrinking helps you find a smaller valid one).

3. State Management Overhead ​

Don't overcomplicate the state.

• Need distinct count? Use a Hash Map (dict) or set.
• Need sum? Just use an integer.
• Need character frequency? Use an array of size 26 (if only lowercase English letters) for $O(1)$ space.

Complexity ​

• Time Complexity: $O(N)$.
  • The right pointer moves $N$ times.
  • The left pointer moves at most $N$ times.
  • Total operations $\approx 2N$, which simplifies to linear time.
• Space Complexity: $O(K)$ or $O(1)$.
  • Depends on the auxiliary structure used to store window state (e.g., a map storing $K$ distinct characters).

Common Questions ​

See how the template applies to real LeetCode problems:

1. Longest Substring Without Repeating Characters (LC 3)

   • Synopsis: Given a string s, find the length of the longest substring without duplicate characters.
   • Signal: "Longest substring," "no repeating."
   • State: A set or dict (index map) to track characters.
   • Logic: Expand right. If s[right] is in set, shrink left until it's removed. Update max length.

2. Minimum Size Subarray Sum (LC 209)

   • Synopsis: Given an array of positive integers and a target target, find the minimal length of a contiguous subarray whose sum is greater than or equal to target.
   • Signal: "Minimal length," "sum $\ge$ target."
   • State: An integer current_sum.
   • Logic: Expand right, add to sum. While sum >= target, update min length and subtract arr[left].

3. Max Consecutive Ones III (LC 1004)

   • Synopsis: Given a binary array and an integer k, return the max number of consecutive 1's if you can flip at most k 0's.
   • Signal: "Longest," "flip at most K zeros."
   • State: Integer zeros_count.
   • Logic: Expand right. If 0, increment count. While count > K, shrink left.

4. Permutation in String (LC 567)

   • Synopsis: Given two strings s1 and s2, return true if s2 contains a permutation of s1.
   • Signal: Fixed length (must match s1 length).
   • State: Frequency array (size 26).
   • Logic: Fixed-size window. No while loop for shrinking—just if window_size > len(s1): left += 1.

Next Steps ​

Now that you have the foundation, let's refine your understanding of the two main variations: