What is Sliding Window?

The Sliding Window is a powerful technique for solving problems that involve contiguous sequences or subarrays within a given list or string.

Instead of recalculating the result for every possible subarray from scratch, we reuse previous computations, “sliding” the window forward and updating the result incrementally. This reduces time complexity significantly — often from O(n²) to O(n).

When to Use Sliding Window?

Sliding Window technique is applicable when:

1. The problem involves contiguous subarrays or substrings.
2. You’re asked to find:
   • Maximum or minimum sum of subarrays of size k.
   • Longest or shortest subarray satisfying a condition.
   • Count of subarrays/substrings meeting a condition.
3. Brute-force solution involves nested loops and recalculating values repeatedly.

Key Phrases in Problem Statements:

• “Find the maximum/minimum sum of k consecutive elements”
• “Find the longest substring/subarray with…”
• “Window of size k”
• “Contiguous sequence with certain properties”

Types of Sliding Window

There are two main types of sliding windows:

1. Fixed-size sliding window
   • The window size is fixed (e.g., find max sum of subarray of size k)
   • Example problems:
     • Maximum sum of k consecutive elements
     • Average of subarrays of size k
2. Variable-size sliding window
   • The window size changes dynamically depending on conditions
   • Example problems:
     • Longest substring with no repeating characters
     • Smallest subarray with a sum greater than or equal to S

Sliding Window vs Brute Force

Brute-force example (O(n²)):

def max_sum_brute_force(arr, k):
    max_sum = float('-inf')
    for i in range(len(arr) - k + 1):
        current_sum = sum(arr[i:i+k])
        max_sum = max(max_sum, current_sum)
    return max_sum

Sliding Window optimized (O(n)):

def max_sum_sliding_window(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # Slide the window
        max_sum = max(max_sum, window_sum)

    return max_sum

Step-by-Step Approach

For Fixed-Size Window:

1. Initialize window – Compute the sum (or other metric) for the first k elements.
2. Slide the window – From index k to end:
   • Add the new element entering the window.
   • Subtract the element that is leaving the window.
3. Update your result – Check if this new window gives a better result.

For Variable-Size Window:

1. Use two pointers: start and end to define the window.
2. Expand end to grow the window until a condition is met.
3. When the condition is violated, shrink the window from start.
4. Track the best result as you expand and contract the window.

Examples

1. Fixed-size window – Max sum of subarray of size k

Problem: Given an array of integers and a number k, find the maximum sum of a subarray of size k.

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

2. Variable-size window – Longest substring with all unique characters

Problem: Given a string, find the length of the longest substring without repeating characters.

def longest_unique_substring(s):
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

3. Variable-size window – Minimum size subarray with sum ≥ target

Problem: Given an array of positive integers and a target sum, find the minimum length of a subarray whose sum is ≥ target.

def min_subarray_len(target, nums):
    left = 0
    total = 0
    min_len = float('inf')

    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            min_len = min(min_len, right - left + 1)
            total -= nums[left]
            left += 1

    return min_len if min_len != float('inf') else 0

Tips to Identify Sliding Window Problems

• Look for phrases like “subarray”, “substring”, or “consecutive”.
• Check if the brute-force solution has nested loops iterating over ranges — that’s a strong hint.
• If constraints are tight (like n ≤ 10⁵), brute-force won’t work; you need O(n) or O(n log n) solutions.
• If you can update the result by removing the effect of one element and adding another, think of sliding window.

Problem: Longest Substring Without Repeating Characters

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

---

Examples

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

Goal

We are asked to find the length of the longest substring that has no repeated characters.

This is a sliding window problem with a variable-size window, where:

• The window will expand until a duplicate is found.
• Once a duplicate is found, shrink the window from the left until all characters in the window are unique again.

---

Brute Force (Inefficient)

Check all substrings and return the maximum length where all characters are unique.

Time Complexity: O(n³)

---

Optimized Approach: Sliding Window

Intuition

Use a sliding window defined by two pointers (left, right) and a set or map to store characters currently in the window.
Slide right to expand, and slide left to shrink whenever there’s a repeated character.

---

Step-by-Step Algorithm

1. Create a set to store characters in the current window.
2. Initialize left = 0 and maxLength = 0.
3. Move right pointer one character at a time:
   • If s[right] is not in the set:
     Add it, update maxLength.
   • If it is in the set:
     Remove characters from the left (left++) until the duplicate is removed.
4. Continue until right reaches the end of the string.

import java.util.HashSet;
import java.util.Set;

public class LongestSubstringWithoutRepeatingCharacters {

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

        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);

            while (charSet.contains(currentChar)) {
                charSet.remove(s.charAt(left));
                left++;
            }

            charSet.add(currentChar);
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingCharacters solution = new LongestSubstringWithoutRepeatingCharacters();
        String input = "abcabcbb";
        System.out.println("Length of longest substring: " + solution.lengthOfLongestSubstring(input));
    }
}

Summary

• Sliding Window is an optimization for problems involving contiguous segments.
• It transforms O(n²) brute-force solutions into O(n) by maintaining state as the window moves.
• Identify it when the problem involves contiguous subarrays or substrings and requires calculating something over them.
• Choose fixed-size or variable-size depending on problem constraints.