Sliding Window Technique in DSA

What is the Sliding Window Technique?

The Sliding Window Technique is an optimization strategy for problems involving linear data structures like arrays or strings. It helps reduce the time complexity from O(n²) to O(n) in many cases by avoiding unnecessary re-computation.

Instead of recalculating results for every subarray or substring, we "slide" a window across the structure — updating the result incrementally.

When to Use

• When you're asked to find subarrays/substrings with specific properties (like sum, max, unique elements).
• When brute-force gives TLE due to overlapping computations.
• When input is linear (array, list, or string) and needs contiguous operations.

Types of Sliding Windows

1. Fixed-size Sliding Window

You know the window size (say k), and the goal is to perform operations over every subarray of size k.

Common Example:

Find the maximum sum of any subarray of size k.

Pseudocode

class SlidingWindowFixed {
    function maxSum(arr, k):
        n = length(arr)
        windowSum = sum of first k elements
        maxSum = windowSum

        for i = k to n-1:
            windowSum = windowSum + arr[i] - arr[i - k]
            maxSum = max(maxSum, windowSum)

        return maxSum
}

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

2. Variable-size Sliding Window

Window size changes dynamically based on the conditions. You expand the window by moving the right pointer and shrink it by moving the left pointer until conditions are satisfied.

Common Example:

Find the length of the longest substring with at most K distinct characters.

Pseudocode

class SlidingWindowVariable {
    function longestSubstringWithKDistinct(s, k):
        left = 0
        right = 0
        freqMap = {}
        maxLen = 0

        while right < length(s):
            add s[right] to freqMap
            while size of freqMap > k:
                decrement freqMap[s[left]]
                if freqMap[s[left]] == 0:
                    remove s[left] from freqMap
                left += 1
            maxLen = max(maxLen, right - left + 1)
            right += 1

        return maxLen
}

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(k) — for hash map

Real-World Applications

• Maximum sum subarray of size k
• Longest substring with k unique characters
• Minimum window substring
• Count of anagrams
• Subarrays with product less than k

Example 1: Longest Substring with K Unique Characters

Problem Statement:

Given a string s and an integer k, find the length of the longest substring that contains exactly k unique characters.

For example:

• s = "aabbcc", k = 2 → Output: 4 (longest substrings are "aabb", "bbcc")
• s = "aaabbb", k = 1 → Output: 3 (longest substrings are "aaa" or "bbb")
• s = "abcba", k = 2 → Output: 3 (longest substrings are "bcb" or "cbc")

Why Sliding Window?

Using a sliding window is efficient for problems that require processing substrings or subarrays. Instead of generating all substrings and checking each, we maintain a dynamic window with exactly k unique characters and slide it to explore new substrings.

Step-by-step Sliding Window Approach:

1. Initialize two pointers: left and right for the sliding window.
2. Use a hash map charCount to count characters in the window.
3. Expand the window by moving right and updating charCount.
4. If unique characters exceed k, shrink the window by moving left.
5. Update the result whenever exactly k unique characters are found.

Pseudocode

// Function to find longest substring with k unique characters
function longestKUniqueSubstring(s, k):
    left = 0
    right = 0
    maxLen = 0
    charCount = empty map

    while right < length of s:
        // Add current character to map
        charCount[s[right]] += 1

        // If unique characters > k, shrink window
        while size of charCount > k:
            charCount[s[left]] -= 1
            if charCount[s[left]] == 0:
                remove s[left] from charCount
            left += 1

        // If exactly k unique characters, update maxLen
        if size of charCount == k:
            maxLen = max(maxLen, right - left + 1)

        right += 1

    return maxLen

Why It Works:

This approach dynamically adjusts the window and ensures that we are always considering substrings with at most k unique characters. When exactly k are present, we update the maximum length seen so far.

Time Complexity:

• O(n) — Each character is added and removed from the window at most once.

Space Complexity:

• O(k) — To store k unique characters in the hash map.

Sliding window techniques like this are crucial in substring problems where the window size or character frequency needs to be tracked. It’s much more efficient than brute-force methods and can be easily adapted to variations of the problem.

Benefits of Sliding Window

• Efficient: Reduces nested loops to linear scans
• Scalable: Works great for large input sizes
• Simple Logic: Easy to understand and implement incrementally

Limitations

• Works only on contiguous (adjacent) elements
• Not useful when the solution depends on non-adjacent elements
• Edge cases (empty window, all unique, etc.) must be handled carefully

Conclusion

The Sliding Window technique is a must-know strategy for solving linear structure problems efficiently. It transforms brute-force nested loop solutions into linear-time solutions by reusing previous computations. Mastering fixed and variable window problems unlocks a broad class of optimization problems in DSA interviews and competitive programming.