Shortest Sliding Window

Use Cases

Use Case	Description	Example
Finding the Shortest Substring Containing All Characters	Given a string and a set of characters, find the length of the shortest substring that contains all the characters from the set.	For the string "ADOBECODEBANC" and the set `{'A', 'B', 'C'}`, the shortest substring is "BANC", with a length of 4.
Finding the Shortest Subarray with a Given Sum	Given an array of integers, find the length of the shortest contiguous subarray that sums to a specified value.	In the array [1, 2, 3, 4, 5] with a target sum of 11, the shortest subarray is [4, 5], with a length of 2.
Finding the Shortest Window to Include All Elements	Given an array of integers, find the length of the shortest contiguous subarray that contains all distinct elements from the array.	For the array [1, 2, 1, 2, 3], the shortest window that contains all distinct elements 3 is [1, 2, 3], with a length of 3.

Code Template

Initializes variables

res: Initialize result as infinity
left indicates the starting index of the current substring being evaluated.
state is used to keep track of the counts of characters (or elements) within the current window defined by the indices between left and right

Shrink current window

Iterate through the string, adding the character at index i to the state dictionary to expand the sliding window.
In the while loop, Update the minimum res size if valid

Clean up and update result

Remove the character from state if its count is zero.
Return -1 if no valid window was found.

Implement valid() function

The valid() function will return True when state contains at least 10 distinct characters.

def shortest_valid(s):
    res = float('inf')
    left = 0
    state = defaultdict(int)

Common mistakes

Wrong State Cleanup

# Wrong: forgetting to cleanup state
state[s[left]] -= 1
left += 1  # Forgot to delete zero count
# Wrong: incorrect cleanup condition
if state[s[left]] <= 0:  # Should be exactly 0
    del state[s[left]]
# Correct:
state[s[left]] -= 1
if state[s[left]] == 0:
    del state[s[left]]
left += 1

Wrong Result Initialization/Return

# Wrong: incorrect initialization
res = -1  # Should be inf for minimum
# Wrong: incorrect return condition
return res if res != float('inf') else 0  # Wrong default
# Correct:
res = float('inf')
return -1 if res == float('inf') else res

Issues and consideration

209. Minimum Size Subarray Sum

class Solution:
    def minSubArrayLen(self, target, nums):
        res = float('inf')
        left = 0
        current_sum = 0
        
        for i in range(len(nums)):
            current_sum += nums[i]
            # While the current sum is valid (i.e., greater than or equal to target)
            while self.valid(current_sum, target):
                res = min(res, i - left + 1)
                current_sum -= nums[left]
                left += 1                 
        return 0 if res == float('inf') else res  # Return 0 if no valid subarray found

    def valid(self, current_sum, target):
        return current_sum >= target

Shortest Sliding Window

Use Cases

Code Template

Initializes variables

Shrink current window

Clean up and update result

Implement valid() function

Common mistakes

Issues and consideration

Related Problem

Resources