📘 Sliding Window Technique

🔍 What Is the Sliding Window Technique?

The Sliding Window is a powerful technique used to reduce the time complexity of problems involving contiguous subarrays or substrings.

Instead of using nested loops (\(O(n^2)\)), we “slide” a window of fixed or variable size across the input, adjusting it as we go — reducing most problems to \(O(n)\) time.

When to Use Sliding Window

• You need to find or optimize subarrays/substrings (e.g., longest, smallest, total).

• The input is linear (array or string).

• You’re looking for problems involving:

  • Sum / Count / Max / Min of a subarray
  • Substring with unique or repeated elements
  • Fixed or variable-sized window

🪟 Sliding Window Pattern

Template for fixed-size window

Find Max sum of subarray of size K

def sliding_window_fixed(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

Template for variable-size window

def sliding_window_variable(s):
    window = {}
    left = 0
    result = 0

    for right in range(len(s)):
        # Expand window by adding s[right]
        # window logic here...

        while <some_condition>:  # shrink
            # Shrink window from the left
            left += 1

        result = max(result, right - left + 1)
    return result

Ex : Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    seen = {}
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len