DSA · Lesson 4 of 17

Sliding Window

⏱ 15 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 5 practice problems

Keep a window over a contiguous range and update it in O(1) as it slides. The go-to pattern for “longest / shortest / best subarray or substring”.

The idea

Many questions ask about the best contiguous subarray or substring. Re-computing each window from scratch is O(n·k). A sliding window keeps running state (a sum, counts, a set) and updates it as the right edge moves in and the left edge moves out, so each element enters and leaves once: O(n).

Two flavours

Fixed size k: add a[r], remove a[r − k], record the answer. Examples: max sum of k elements, averages, sliding window maximum (with a monotonic deque).

Variable size: expand right every step; while the window breaks a rule, shrink from left. Record the best valid window. Examples:

Longest substring without repeating characters (rule: no duplicates)
Longest substring with at most k changes (rule: len − maxFreq ≤ k)
Minimum window substring (shrink while the window still covers t)

Recognise it

“contiguous subarray / substring”
“longest”, “shortest”, “at most k”, “maximum sum of size k”
All values positive (so growing the window only increases the sum)

Code template

# Variable-size window template
def longest_valid(s):
    count = {}
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1          # 1) grow: add s[right]
        while count[ch] > 1:                       # 2) shrink while invalid
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)         # 3) record the valid window
    return best

# Fixed-size window: max sum of k consecutive values
def max_sum_k(a, k):
    s = sum(a[:k]); best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]
        best = max(best, s)
    return best

// Variable-size window template
int longestValid(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        count.merge(ch, 1, Integer::sum);                 // 1) grow
        while (count.get(ch) > 1) {                         // 2) shrink while invalid
            count.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }
        best = Math.max(best, right - left + 1);            // 3) record
    }
    return best;
}

// Fixed-size window: max sum of k consecutive values
int maxSumK(int[] a, int k) {
    int s = 0; for (int i = 0; i < k; i++) s += a[i];
    int best = s;
    for (int r = k; r < a.length; r++) { s += a[r] - a[r - k]; best = Math.max(best, s); }
    return best;
}

// Variable-size window template
int longestValid(const string& s) {
    unordered_map<char, int> count;
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char ch = s[right];
        count[ch]++;                                  // 1) grow
        while (count[ch] > 1) count[s[left++]]--;     // 2) shrink while invalid
        best = max(best, right - left + 1);           // 3) record
    }
    return best;
}

// Fixed-size window: max sum of k consecutive values
int maxSumK(const vector<int>& a, int k) {
    int s = accumulate(a.begin(), a.begin() + k, 0), best = s;
    for (int r = k; r < (int)a.size(); r++) { s += a[r] - a[r - k]; best = max(best, s); }
    return best;
}

// Variable-size window template
function longestValid(s) {
  const count = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    count.set(ch, (count.get(ch) || 0) + 1);       // 1) grow
    while (count.get(ch) > 1) {                     // 2) shrink while invalid
      count.set(s[left], count.get(s[left]) - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);        // 3) record
  }
  return best;
}

// Fixed-size window: max sum of k consecutive values
function maxSumK(a, k) {
  let s = a.slice(0, k).reduce((x, y) => x + y, 0), best = s;
  for (let r = k; r < a.length; r++) { s += a[r] - a[r - k]; best = Math.max(best, s); }
  return best;
}

Complexity

O(n) time, because left and right each move at most n times. Space is O(1), or O(alphabet) for character counts.

Practise this pattern (5 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
16	Best Time to Buy and Sell Stock	Easy
17	Longest Substring Without Repeating Characters	Medium
18	Longest Repeating Character Replacement	Medium
19	Minimum Window Substring	Hard
20	Sliding Window Maximum	Hard

Common mistakes

Using a sliding window when values can be negative and you need an exact sum: use prefix sums + a hash map.
Updating the answer at the wrong moment: for the longest window, record after shrinking; for the shortest, record inside the shrinking loop.
Off-by-one errors in the window length: it is right − left + 1.

Check yourself: why is the variable window O(n) even though it has a while-loop inside a for-loop?

The inner loop only moves left forward, and left can advance at most n times in total. Summed over the whole run, that is 2n moves.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar