Sliding Window

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: Easy. ROI: High.

Other common names: Fixed-size / variable-size window (when distinguishing).

When to use: Use when the problem asks for a contiguous subarray or substring that satisfies a condition (max sum of size k, longest substring with at most k distinct characters, etc.).

Idea: Maintain a window (left and right indices) and slide it while keeping the window valid.

Fixed-size: move both by one each step. Variable-size: expand right, then shrink left as needed.

Time / space: Often O(n) time, O(1) or O(k) extra space.

Example #1 — Max Sum of Subarray of Size K

Find the maximum sum of any contiguous subarray of fixed size k. Use the first window’s sum, then slide one step at a time by adding the new right element and subtracting the one that left.

Sample input and output

arr = [2, 1, 5, 1, 3, 2]
window_size = 3
print(max_sum_subarray(arr, window_size))  # 9  (subarray [5, 1, 3])

• Sample input: arr = [2, 1, 5, 1, 3, 2], window_size = 3.
• Sample output: 9 — the maximum sum of any 3 consecutive elements is 5+1+3 = 9.

Code (with inline comments)

# Max sum of subarray of fixed window_size
def max_sum_subarray(arr, window_size):
    window_sum = sum(arr[:window_size])   # sum of first window [0..window_size-1]
    best = window_sum

    for right_index in range(window_size, len(arr)):
        window_sum += arr[right_index] - arr[right_index - window_size]  # slide: add new right, drop left
        best = max(best, window_sum)  # max is a python built-in; returns the larger of the two
    return best

Line-by-line:

• window_sum = sum(arr[:window_size]) — We compute the sum of the first window: elements from index 0 to window_size−1. arr[:window_size] is a slice: the first window_size elements.
• best = window_sum — So far, the best sum we’ve seen is this first window.
• for right_index in range(window_size, len(arr)): — We’ll slide the window one step to the right each time. right_index is the new rightmost index of the window; the window is then [right_index - window_size + 1 .. right_index].
• window_sum += arr[right_index] - arr[right_index - window_size] — To slide: add the new element at the right (arr[right_index]) and subtract the element that just left the window at the left (arr[right_index - window_size]). That keeps the sum for the current window without recalculating from scratch.
• best = max(best, window_sum) — Update the best sum if this window is better.
• return best — Return the maximum sum of any contiguous subarray of length window_size.

Execution trace (numbered list)

Trace for arr = [2, 1, 5, 1, 3, 2], window_size = 3. Initial window [2,1,5], window_sum=8, best=8.

1. Step 1: right_index=3, window [1,5,1], window_sum = 8−2+1 = 7, best = 8.
2. Step 2: right_index=4, window [5,1,3], window_sum = 7−1+3 = 9, best = 9.
3. Step 3: right_index=5, window [1,3,2], window_sum = 9−5+2 = 6, best = 9.
4. Return 9 (best sum from window [5, 1, 3]).

Execution trace (code with step comments)

arr = [2, 1, 5, 1, 3, 2]
window_size = 3
window_sum = sum(arr[:window_size])   # 8
best = window_sum                     # 8

# Step 1: right_index=3, add arr[3]=1, drop arr[0]=2
window_sum += arr[3] - arr[0]   # 8 + 1 - 2 = 7
best = max(best, window_sum)   # 8

# Step 2: right_index=4, add arr[4]=3, drop arr[1]=1
window_sum += arr[4] - arr[1]   # 7 + 3 - 1 = 9
best = max(best, window_sum)   # 9

# Step 3: right_index=5, add arr[5]=2, drop arr[2]=5
window_sum += arr[5] - arr[2]   # 9 + 2 - 5 = 6
best = max(best, window_sum)   # 9
# Return 9

Execution trace (ASCII diagram)

Window slides right one index each step; brackets show the current window.

Initial: [ 2,  1,  5,  1,  3,  2 ]   window_sum=8, best=8
            [-------]

Step 1:  [ 2,  1,  5,  1,  3,  2 ]   window_sum=7, best=8
               [-------]

Step 2:  [ 2,  1,  5,  1,  3,  2 ]   window_sum=9, best=9
                  [-------]

Step 3:  [ 2,  1,  5,  1,  3,  2 ]   window_sum=6, best=9
                     [-------]
Return 9

Example #2 — Longest Substring With at Most K Distinct Characters

Find the length of the longest substring that contains at most K distinct characters. Use a variable-size window: expand right, then shrink left (removing one character at a time) until the window has at most K distinct characters.

Sample input and output

print(longest_substring_k_distinct("eceba", 2))   # 3  ("ece" or "eba")
print(longest_substring_k_distinct("aaabbcc", 1)) # 3  ("aaa")

• Sample input: s = "eceba", k = 2.
• Sample output: 3 — longest substring with at most 2 distinct characters is “ece” or “eba” (length 3).

Code (with inline comments)

from collections import defaultdict

def longest_substring_k_distinct(s, k):
    if k == 0:
        return 0
    left = 0
    freq = defaultdict(int)   # character -> count in current window
    best = 0
    for right in range(len(s)):
        freq[s[right]] += 1    # expand: add character at right
        while len(freq) > k:   # shrink until window has at most k distinct
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

Line-by-line:

• freq = defaultdict(int) — Count of each character in the current window. len(freq) is the number of distinct characters.
• for right in range(len(s)): — Expand the window by including the character at right.
• freq[s[right]] += 1 — Add the new character to the window.
• while len(freq) > k: — If we have more than k distinct characters, shrink from the left until we don’t.
• freq[s[left]] -= 1 … del freq[s[left]] — Remove the leftmost character from the window; if its count hits 0, drop it from the dict so len(freq) decreases.
• best = max(best, right - left + 1) — Window [left..right] is valid; its length is right - left + 1.

Execution trace (numbered list)

For s = "eceba", k = 2:

1. Step 1: right=0, add ‘e’, freq = {e:1}, len=1 ≤ 2, best=1.
2. Step 2: right=1, add ‘c’, freq = {e:1,c:1}, len=2 ≤ 2, best=2.
3. Step 3: right=2, add ‘e’, freq = {e:2,c:1}, len=2 ≤ 2, best=3.
4. Step 4: right=3, add ‘b’, freq = {e:2,c:1,b:1}, len=3 > 2. Shrink: drop ‘e’ (left=0), left=1; drop ‘c’, left=2; drop ‘e’, left=3. freq = {b:1}. best=3.
5. Step 5: right=4, add ‘a’, freq = {b:1,a:1}, len=2 ≤ 2, best=3. Return 3.

Execution trace (code with step comments)

s, k = "eceba", 2
left = 0
freq = {}
# right=0: add 'e' → freq={e:1}, best=1
# right=1: add 'c' → freq={e:1,c:1}, best=2
# right=2: add 'e' → freq={e:2,c:1}, best=3
# right=3: add 'b' → freq={e:2,c:1,b:1}, len>2 → shrink to left=3, freq={b:1}
# right=4: add 'a' → freq={b:1,a:1}, best=3
# return 3

Execution trace (ASCII diagram)

Variable window; shrink from the left when distinct count exceeds K.

s = "e c e b a"   k = 2
    [---]         "ece" has 2 distinct → length 3, best=3
       [---]      "eba" has 2 distinct → length 3
    L   R

Example #3 — Longest Substring Without Repeating Characters

Find the length of the longest substring with all distinct characters (no repeats). Expand right; when the new character is already in the window, shrink from the left until that character is removed.

Sample input and output

print(longest_substring_no_repeat("abcabcbb"))  # 3  ("abc")
print(longest_substring_no_repeat("bbbbb"))     # 1
print(longest_substring_no_repeat("pwwkew"))   # 3  ("wke" or "kew")

• Sample input: s = "abcabcbb".
• Sample output: 3 — longest substring without repeating characters is “abc” (length 3).

Code (with inline comments)

def longest_substring_no_repeat(s):
    left = 0
    seen = set()   # characters in current window
    best = 0
    for right in range(len(s)):
        while s[right] in seen:   # shrink until we drop the duplicate
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

Line-by-line:

• seen = set() — Characters currently in the window. We need no duplicates, so a set is enough.
• for right in range(len(s)): — Expand the window by including the character at right.
• while s[right] in seen: — The new character is already in the window; shrink from the left until we remove the previous occurrence of s[right].
• seen.remove(s[left]); left += 1 — Remove the leftmost character from the window and advance left.
• seen.add(s[right]) — Add the character at right to the window (now it’s the only occurrence in the window).
• best = max(best, right - left + 1) — Current window length is right - left + 1.

Execution trace (numbered list)

For s = "abcabcbb":

1. Step 1: right=0, ‘a’ not in seen, add it, best=1.
2. Step 2: right=1, ‘b’ not in seen, add it, best=2.
3. Step 3: right=2, ‘c’ not in seen, add it, best=3.
4. Step 4: right=3, ‘a’ in seen. Shrink: remove ‘a’ (left=0), left=1. Add ‘a’, best=3.
5. Step 5: right=4, ‘b’ in seen. Shrink: remove ‘b’, left=2. Add ‘b’, best=3.
6. Continue; window never exceeds length 3. Return 3.

Execution trace (code with step comments)

s = "abcabcbb"
left = 0
seen = set()
# right=0: 'a' not in seen → add, best=1
# right=1: 'b' not in seen → add, best=2
# right=2: 'c' not in seen → add, best=3
# right=3: 'a' in seen → remove s[0]='a', left=1; add 'a', best=3
# right=4: 'b' in seen → remove s[1]='b', left=2; add 'b', best=3
# ... return 3

Execution trace (ASCII diagram)

Shrink from the left until the duplicate is gone; then add the new character.

s = "a b c a b c b b"
    [-----]            "abc" length 3
       [-----]          "bca" length 3
          [-----]       "cab" length 3
    L     R