Understanding the Sliding Window Algorithm: A Comprehensive Guide with Python Example

Algorithm Updated on April 13, 2025

Table of Contents

What is the Sliding Window Algorithm?

The sliding window algorithm is a technique used to solve problems involving arrays or strings by maintaining a "window" of elements that satisfies a given condition. Instead of processing the entire dataset repeatedly, the algorithm slides this window across the data, expanding or shrinking it as needed, which optimizes time complexity.

At its core, the algorithm uses two pointers—typically left and right—to define the window's boundaries. The window slides by adjusting these pointers based on problem-specific constraints, making it ideal for finding subarrays or substrings with properties like a specific sum, length, or character count.

Types of Sliding Windows

The sliding window algorithm comes in two main flavors:

  1. Fixed-size Window:

    • The window maintains a constant size.
    • Example: Find the maximum sum of a subarray of size k.
    • Approach: Compute the result for the first window, then slide it by moving both pointers one step, updating calculations efficiently.

  2. Variable-size Window:

    • The window size changes dynamically based on constraints.
    • Example: Find the longest substring with at most k distinct characters.
    • Approach: Expand the window by moving right, shrink it by moving left when the condition is violated, and track the optimal result.

How It Works: General Approach

The sliding window algorithm follows these steps:

  1. Initialize: Set up pointers (left, right) and variables (e.g., sum, count, result).
  2. Expand: Move right to include new elements, updating relevant data (e.g., sum, frequency).
  3. Shrink (if needed): If the window violates the problem's condition, move left to exclude elements until the window is valid again.
  4. Update Result: Track the optimal solution (e.g., maximum/minimum window size, sum).
  5. Repeat: Continue until right reaches the end of the array or string.

This approach reduces brute-force complexity (e.g., O(n²) to O(n)) by ensuring each element is processed a limited number of times.

Example Problem: Longest Substring Without Repeating Characters

Let’s apply the sliding window algorithm to a classic problem to see it in action.

Problem Statement

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

Examples:

  • Input: s = "abcabcbb" → Output: 3 (substring: "abc")
  • Input: s = "bbbbb" → Output: 1 (substring: "b")
  • Input: s = "pwwkew" → Output: 3 (substring: "wke")
  • Input: s = "" → Output: 0

This is a variable-size sliding window problem, as we need to find the longest substring where all characters are unique.

Solution in Python

Here’s a Python implementation using a sliding window with a set to track characters:

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    max_length = 0
    left = 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

How the Solution Works

  • Initialization:
    • char_set stores unique characters in the current window.
    • max_length tracks the longest valid substring.
    • left starts at index 0.
  • Sliding Window:
    • Move right to include s[right].
    • If s[right] is already in char_set, shrink the window by removing s[left] and incrementing left until no duplicate exists.
    • Add s[right] to char_set and update max_length with the current window size (right - left + 1).
  • Termination: When right reaches the end, return max_length.

Walkthrough for s = "abcabcbb":

  • right=0: char_set={a}, window=[a], max_length=1.
  • right=1: char_set={a,b}, window=[a,b], max_length=2.
  • right=2: char_set={a,b,c}, window=[a,b,c], max_length=3.
  • right=3: a is duplicate, remove a (left=1), char_set={b,c}, add a, char_set={b,c,a}, window=[b,c,a], max_length=3.
  • right=4: b is duplicate, remove b (left=2), char_set={c,a}, add b, char_set={c,a,b}, window=[c,a,b], max_length=3.
  • Continue until right=7, final max_length=3.

Tests

To ensure the solution is robust, we use Python’s unittest module to test various cases:

import unittest

class TestLengthOfLongestSubstring(unittest.TestCase):
    def test_normal_case(self):
        self.assertEqual(length_of_longest_substring("abcabcbb"), 3)

    def test_all_same_characters(self):
        self.assertEqual(length_of_longest_substring("bbbbb"), 1)

    def test_no_repeating(self):
        self.assertEqual(length_of_longest_substring("pwwkew"), 3)

    def test_empty_string(self):
        self.assertEqual(length_of_longest_substring(""), 0)

    def test_single_character(self):
        self.assertEqual(length_of_longest_substring("a"), 1)

    def test_all_unique(self):
        self.assertEqual(length_of_longest_substring("abcdef"), 6)

    def test_spaces_and_special(self):
        self.assertEqual(length_of_longest_substring("a b$c"), 5)

if __name__ == "__main__":
    unittest.main()

Test Cases Explained:

  • Normal case: "abcabcbb" tests mixed repeating and non-repeating characters.
  • All same characters: "bbbbb" ensures the smallest window (size 1).
  • No repeating: "pwwkew" checks for a substring like "wke".
  • Empty string: "" handles the edge case.
  • Single character: "a" tests minimal input.
  • All unique: "abcdef" confirms the entire string as the answer.
  • Spaces and special: "a b$c" verifies handling of non-alphabetic characters.

Running the tests yields:

......
----------------------------------------------------------------------
Ran 7 tests in 0.001s

OK

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. Each character is added and removed at most once, as left and right pointers only move forward.
  • Space Complexity: O(min(m, n)), where m is the size of the character set (e.g., 26 for lowercase letters) and n is the string length, due to the char_set storage.

Applications of Sliding Window

The sliding window algorithm is versatile and applies to many problems, including:

  • Fixed-size: Maximum/minimum sum of a subarray of size k, average of consecutive elements.

  • Variable-size: Longest/shortest substring or subarray with constraints (e.g., at most k distinct characters, no duplicates, specific sum).

  • Common Problems:

    • Two Sum
    • Minimum Window Substring
    • Maximum Points from Cards
    • Longest Substring with At Most K Distinct Characters

By reducing the need for nested loops, the algorithm transforms inefficient solutions into linear or near-linear ones, making it a staple in coding interviews and competitive programming.

Conclusion

The sliding window algorithm is an elegant and efficient technique for tackling array and string problems. By maintaining a dynamic window, it minimizes redundant computations and scales well for large inputs. Our example—finding the longest substring without repeating characters—demonstrates how a variable-size window, paired with a set for tracking uniqueness, solves the problem in linear time.

The included Python solution and comprehensive tests highlight the algorithm’s practicality and robustness. Whether you’re preparing for a coding interview or optimizing real-world applications, mastering the sliding window technique opens the door to solving a wide range of problems efficiently.

If you’re eager to explore further, try applying the algorithm to other problems like finding the maximum sum subarray or the minimum window substring. Happy coding!