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 Sum at Least Target	Given a positive integer array, find the length of the shortest contiguous subarray whose sum is at least a target.	In the array [1, 2, 3, 4, 5] with target 11, the shortest subarray is [3, 4, 5], with length 3.
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 = float('inf'): Start with infinity because we are minimizing the window length.
left is the start of the current window.
state stores whatever the problem needs to decide whether the current window is valid. It can be a frequency map, a running sum, or matched-count variables.

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 valid

For shortest-window problems, update the answer inside the while valid(...) loop.
After recording the valid window length, remove nums[left] and move left forward to see if a smaller valid window exists.
If a frequency drops to zero, delete it so state checks like len(state) stay correct.

Return problem-specific empty answer

If res is still infinity, no valid window was found.
The empty answer depends on the problem: 0 for minimum length problems like 209, "" for minimum substring problems, or -1 if the problem asks for it.

Implement valid() function

valid(state) is the only part that changes between problems.
Examples: current_sum >= target, formed == required, or len(state) == need_count.

def shortest_window(nums):
    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):
        # Same template; here the "state" is a running sum instead of a frequency map.
        def valid(state):
            return state >= target

        res = float('inf')
        left = 0
        state = 0

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

            while valid(state):
                res = min(res, right - left + 1)
                y = nums[left]
                state -= y
                left += 1

        return 0 if res == float('inf') else res

76. Minimum Window Substring

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # Same template; valid when the window covers every required character count.
        def valid(state):
            return formed == required

        need = Counter(t)
        required = len(need)
        formed = 0
        res = float('inf')
        ans = ""
        left = 0
        state = defaultdict(int)

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

            while valid(state):
                if right - left + 1 < res:
                    res = right - left + 1
                    ans = s[left:right + 1]

                y = s[left]
                state[y] -= 1
                if y in need and state[y] < need[y]:
                    formed -= 1
                if state[y] == 0:
                    del state[y]
                left += 1

        return ans

1234. Replace the Substring for Balanced String

class Solution:
    def balancedString(self, s: str) -> int:
        # Same template; state tracks counts outside the current window.
        def valid(state):
            return all(state[ch] <= target for ch in "QWER")

        n = len(s)
        target = n // 4
        res = float('inf')
        left = 0
        state = Counter(s)

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

            while valid(state):
                res = min(res, right - left + 1)
                y = s[left]
                state[y] += 1
                left += 1

        return 0 if res == float('inf') else res

Shortest Sliding Window

Use Cases

Code Template

Initializes variables

Expand the right boundary

Shrink while valid

Return problem-specific empty answer

Implement valid() function

Common mistakes

Issues and consideration

Related Problem

Resources