Breaking Down Sliding Window

Sliding window is a technique for problems that ask about a contiguous subarray or substring — something like "find the longest / shortest / count of subarrays that satisfy some condition."

The brute force approach checks every possible subarray, which is O(n²). Sliding window brings that down to O(n) by maintaining two pointers — a left and a right — that define the current window. The right pointer expands the window by moving forward, and the left pointer shrinks it when the window becomes invalid.

The key insight is that we never need to start over from scratch. When the window breaks a condition, we just move the left pointer forward until it's valid again.

Demo — Longest Substring Without Repeating Characters

Most sliding window problems follow this exact skeleton:

l = 0
for r in range(len(s)):
    # add s[r] to window
 
    while window is invalid:
        # remove s[l] from window
        l += 1
 
    # update result

The problems below all use this pattern — each one just adds a different condition for what makes a window "valid."

3. Longest Substring Without Repeating Characters

Classic sliding window. Keep a window where all characters are unique. When a duplicate appears, move the left pointer.

HashSet version — left moves one step at a time:

def lengthOfLongestSubstring(s):
    charSet = set()
    l = 0
    res = 0
 
    for r in range(len(s)):
        while s[r] in charSet:
            charSet.remove(s[l])
            l += 1
        charSet.add(s[r])
        res = max(res, r - l + 1)
 
    return res

HashMap version — left jumps directly:

def lengthOfLongestSubstring(s):
    charMap = {}
    l = 0
    res = 0
 
    for r in range(len(s)):
        if s[r] in charMap:
            l = max(l, charMap[s[r]] + 1)
        charMap[s[r]] = r
        res = max(res, r - l + 1)
 
    return res

The HashMap version is more efficient because left jumps directly to the right position instead of moving one step at a time.

One important thing — l = max(l, charMap[s[r]] + 1) needs max because the stored index might be outside the current window. Without it, left could move backwards.

Time: O(n) / Space: O(n)

424. Longest Repeating Character Replacement

Given a string and k replacements, find the longest substring where all characters can be made the same.

The key insight — a window is valid if (window size - max frequency) <= k.

def characterReplacement(s, k):
    countMap = {}
    l = 0
    res = 0
    maxf = 0
 
    for r in range(len(s)):
        countMap[s[r]] = 1 + countMap.get(s[r], 0)
        maxf = max(maxf, countMap[s[r]])
 
        while (r - l + 1) - maxf > k:
            countMap[s[l]] -= 1
            l += 1
 
        res = max(res, r - l + 1)
 
    return res

Why maxf never decreases:

maxf only goes up, never down. Even if the current window doesn't actually have that frequency anymore, we don't update it downward. This works because we only care about finding a larger window than what we've already seen. A smaller window can't beat our current best, so we just maintain the size.

Time: O(n) / Space: O(1) (at most 26 characters)

340. Longest Substring with At Most K Distinct Characters

Keep a window where the number of distinct characters stays at or below k.

def lengthOfLongestSubstringKDistinct(s, k):
    count = {}
    l = 0
    res = 0
 
    for r in range(len(s)):
        count[s[r]] = 1 + count.get(s[r], 0)
 
        while len(count) > k:
            count[s[l]] -= 1
            if count[s[l]] == 0:
                del count[s[l]]
            l += 1
 
        res = max(res, r - l + 1)
 
    return res

Time: O(n) / Space: O(k)

159. Longest Substring with At Most Two Distinct Characters

Special case of 340 where k = 2. Same exact code, just pass k = 2.

992. Subarrays with K Different Integers

This one is trickier. Find the number of subarrays with exactly K distinct integers.

Key insight:

exactly K = atMost(K) - atMost(K-1)

Counting exactly K directly is hard, but atMost(K) is easy — it's the same sliding window pattern from 340.

Method 1: atMost(K) - atMost(K-1)

def subarraysWithKDistinct(nums, k):
    def atMost(k):
        count = {}
        l = 0
        res = 0
 
        for r in range(len(nums)):
            count[nums[r]] = 1 + count.get(nums[r], 0)
 
            while len(count) > k:
                count[nums[l]] -= 1
                if count[nums[l]] == 0:
                    del count[nums[l]]
                l += 1
 
            res += r - l + 1
 
        return res
 
    return atMost(k) - atMost(k - 1)

res += r - l + 1 because at each r, there are exactly r - l + 1 valid subarrays ending at r (starting from anywhere between l and r).

Method 2: Three Pointer (lBase + lMove + r)

Instead of calling atMost twice, we can do it in one pass using two left pointers.

• lMove — actual left boundary of the window (manages the count map)
• lBase — tracks the start of valid "exactly K" subarrays

def subarraysWithKDistinct(nums, k):
    count = {}
    res = 0
    lBase = 0
    lMove = 0
 
    for r in range(len(nums)):
        count[nums[r]] = 1 + count.get(nums[r], 0)
 
        while len(count) > k:
            count[nums[lMove]] -= 1
            if count[nums[lMove]] == 0:
                del count[nums[lMove]]
            lMove += 1
            lBase = lMove
 
        while count.get(nums[lMove], 0) > 1:
            count[nums[lMove]] -= 1
            lMove += 1
 
        if len(count) == k:
            res += lMove - lBase + 1
 
    return res

Time: O(n) / Space: O(n)

Summary

Now try it yourself — start with LC 3 if you haven't already. It's the cleanest intro to the pattern.