Sliding Window Algorithm - Interactive Explainer

lightbulb

The Concept

The Sliding Window technique is an algorithmic pattern used to perform operations on a specific window size of a given array or string. It converts nested loops (O(n²)) into a single loop (O(n)).

For finding the longest substring without repeating characters, we use a dynamic window defined by left and right pointers:

check_circle Expand right to include new characters.
warning If a duplicate is found inside the current window, contract from the left until the duplicate is removed.
ads_click Track the maximum window size encountered.

Solution.cpp

int lengthOfLongestSubstring(string s) {
    vector charIndex(128, -1); // Map char to last index
    int left = 0, maxLength = 0;
    
    for (int right = 0; right < s.length(); right++) {
        // If char seen and inside current window
        if (charIndex[s[right]] >= left) {
            left = charIndex[s[right]] + 1; // Jump left pointer
        }
        charIndex[s[right]] = right; // Update last seen index
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

Algorithm Visualizer

Enter a string to see how the window slides.

arrow_forward_ios L

Variables

left 0

right -

current_char -

maxLength 0

Last Seen Index Map

Map is empty

Current Action

Initialize variables: left = 0, maxLength = 0. Map is empty.

Slow Fast

schedule

Time Complexity: O(N)

Although there's a while loop logic implied by sliding the left pointer (or direct jump in optimized version), each character is visited at most twice (once by right, once by left). In the optimized map version shown, left jumps directly, making it strictly linear scan.

data_usage

Space Complexity: O(min(m, n))

The space is required for the charIndex map (or vector). The size is bounded by the size of the charset m (e.g., 128 for ASCII, 26 for lowercase English). It does not grow with string size n beyond the charset limit.