Longest Sliding Window

Use Cases

Use Case	Description	Example
Finding the Longest Substring Without Repeating Characters	Given a string, find the length of the longest substring that contains no repeating characters.	For the string "abcabcbb", the longest substring without repeating characters is "abc", with a length of 3.
Finding the Longest Substring with At Most K Distinct Characters	Given a string, find the longest substring containing at most `k` distinct characters.	For `"eceba"` and `k = 2`, the answer is `"ece"` with length 3.
Finding the Longest Subarray with At Most K Flips	Given a binary array, find the longest subarray containing at most `k` zeros.	For `[1,1,1,0,0,0,1,1,1,1,0]` and `k = 2`, the answer is 6.

Code Template

Initializes variables

res stores the best valid window length seen so far.
left is the start of the current window.
state stores the information needed to decide whether the current window is valid. For many problems, this is a frequency map.

Expand the right boundary

Move right from left to right across the input.
Add nums[right] into the window state. This is the “expand” step.

Shrink while invalid

while invalid(state): means the current window breaks the problem rule.
Remove nums[left] from the state, then move left forward until the window becomes valid again.
If a frequency drops to zero, delete it so checks like len(state) <= k stay correct.

Update the answer

After the while loop finishes, the window [left, right] is valid.
Update res with the current valid window length.

Define invalid()

invalid(state) is the only part that changes between problems.
Examples: len(state) > k for “at most k distinct”; state[x] > 1 for “no duplicate current character”; zeros > k if you track zeros instead of a map.

def longest_window(nums):
    res = 0
    left = 0
    state = defaultdict(int)

Common mistakes

Wrong State Initialization/Update

# Wrong: forgetting to initialize state
state[s[i]] += 1  # KeyError if not using defaultdict
# Wrong: incorrect state cleanup
if state[s[left]] == 0:  # Should remove key when count is 0
    state[s[left]] -= 1  # Creates negative counts
# Correct:
state = defaultdict(int)
state[s[i]] += 1
if state[s[left]] == 0:
    del state[s[left]]

Wrong Window Boundary Update

# Wrong: incorrect window size calculation
res = max(res, i - left)  # Missing +1 for inclusive range
# Wrong: incorrect left pointer movement
left = i  # Skips too many characters
# Correct:
res = max(res, i - left + 1)
left += 1

Issues and consideration

Input Validation: The function does not validate the input type. If s is not a string, the code will raise errors. Adding a check to ensure s is a string would improve robustness.

3. Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s):
        # Same template; invalid when the current character appears more than once.
        def invalid(state, x):
            return state[x] > 1

        res = 0
        left = 0
        state = defaultdict(int)

        for right in range(len(s)):
            x = s[right]
            state[x] += 1

            while invalid(state, x):
                y = s[left]
                state[y] -= 1
                if state[y] == 0:
                    del state[y]
                left += 1

            res = max(res, right - left + 1)
        return res

159. Longest Substring with At Most Two Distinct Characters

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s):
        # Same template; invalid when the window has more than 2 distinct chars.
        def invalid(state):
            return len(state) > 2

        res = 0
        left = 0
        state = defaultdict(int)

        for right in range(len(s)):
            x = s[right]
            state[x] += 1

            while invalid(state):
                y = s[left]
                state[y] -= 1
                if state[y] == 0:
                    del state[y]
                left += 1

            res = max(res, right - left + 1)
        return res

340. Longest Substring with At Most K Distinct Characters

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s, k):
        # Same template; invalid when the window has more than k distinct chars.
        def invalid(state):
            return len(state) > k

        res = 0
        left = 0
        state = defaultdict(int)

        for right in range(len(s)):
            x = s[right]
            state[x] += 1

            while invalid(state):
                y = s[left]
                state[y] -= 1
                if state[y] == 0:
                    del state[y]
                left += 1

            res = max(res, right - left + 1)
        return res

904. Fruit Into Baskets

class Solution:
    def totalFruit(self, fruits):
        # Same template as "at most 2 distinct"; fruit type is the key.
        def invalid(state):
            return len(state) > 2

        res = 0
        left = 0
        state = defaultdict(int)

        for right in range(len(fruits)):
            x = fruits[right]
            state[x] += 1

            while invalid(state):
                y = fruits[left]
                state[y] -= 1
                if state[y] == 0:
                    del state[y]
                left += 1

            res = max(res, right - left + 1)
        return res

Longest Sliding Window

Use Cases

Code Template

Initializes variables

Expand the right boundary

Shrink while invalid

Update the answer

Define invalid()

Common mistakes

Issues and consideration

Related Problem

Resources