Skip to main content

Shortest Sub{string,array}

while expand + while shrink

Condition for shrink usually will just be the complement/negation/opposite of expansion.

Naive​

209. Minimum Size Subarray Sum​

Explanation

Find the minimum length of a contiguous subarray whose sum is greater than or equal to target.

Expansion:

  • Expand the window by incrementing right, adding to total until it reaches or surpasses the target.

Shrinking:

  • Once the target is met, shrink from the left to potentially reduce window size while still meeting the sum requirement. The logic is integrated within this phase.

Logic:

  • Within the shrinking phase, before decrementing total, update mini to reflect the shortest subarray found.
Analysis
Time
O(n)
  • right and left each advance across nums (length n) at most once, so every element is added to and removed from the window at most once.
Space
O(1)
  • Only left, right, mini, and total are tracked.
FIG. 209 MINIMUM SIZE SUBARRAY SUM● INTERACTIVE
visualization loads as you reach it
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
left = right = 0
mini = float("inf")
total = 0
 
isUnderTarget = lambda i: i < target
 
while right < n:
# Expansion
while right < n and isUnderTarget(total):
total += nums[right]
right += 1
# Shrinking
while left < right and not isUnderTarget(total):
# Logic
mini = min(mini, right - left)
total -= nums[left]
left += 1
return mini if mini != float("inf") else 0

2260. Minimum Consecutive Cards to Pick Up​

Medium·
Explanation

Find the minimum number of consecutive cards needed to pick up at least one pair of matching cards. The window expands until a duplicate is found, then shrinks to find the minimum window containing the pair.

Analysis
Time
O(N)
  • Each card is considered at most once for inclusion and removal.
Space
O(N)
  • The counter could contain an entry for every unique card.
FIG. 2260 MINIMUM CONSECUTIVE CARDS TO PICK UP● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
n = len(cards)
left = right = 0
mini = float("inf")
counter = Counter()
 
hasDuplicate = lambda: counter.distinct_count() < right - left
 
while right < n:
# Expansion
while right < n and not hasDuplicate():
counter[cards[right]] += 1
right += 1
# Shrinking
while left < right and hasDuplicate():
# Logic
mini = min(mini, right - left)
counter[cards[left]] -= 1
left += 1
return mini if mini != float("inf") else -1

Two Strings​

76. Minimum Window Substring​

Hard·
Explanation

Find the smallest window in string s that contains all characters of string t.

  • Cache all frequencies required by t in required_counter.
  • Track frequencies of characters in the window using counter, and maintain required as the count of unique characters still needed.

Expansion:

  • Expand until all required characters are included (required == 0). Decrement required when a character's frequency matches its required count.

Shrinking:

  • Shrink while the requirement still holds. Increment required when a necessary character is removed.

Logic:

  • During shrinking, capture the smallest valid window.
Analysis
Time
O(m + n)
  • m = len(t), n = len(s). Building counter = Counter(t) scans every character of t once - O(m) - then the right/left two-pointer scan visits every character of s at most once each - O(n).
Space
O(1)
  • counter (the single dict-backed Counter, not two) tracks per-character counts for whatever distinct characters appear in s and t; bounded by the fixed English-letter alphabet, so it never grows with m or n.
FIG. 76 MINIMUM WINDOW SUBSTRING● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def minWindow(self, s: str, t: str) -> str:
n = len(s)
left = right = 0
mini = (float("inf"), -1, -1)
counter = Counter(t)
 
hasAllChars = lambda: counter.distinct_count() == 0
 
while right < n:
# Expansion
while right < n and not hasAllChars():
counter[s[right]] -= 1
right += 1
# Shrinking
while left < right and hasAllChars():
# Logic
mini = min(mini, (right - left, left, right))
counter[s[left]] += 1
left += 1
return s[mini[1] : mini[2]] if mini[1] != -1 else ""

Smallest window containing 0, 1 and 2​

Easy·
Explanation

A special case of "Minimum Window Substring" where t = "012". Find the shortest substring that includes all digits "0", "1", and "2" at least once. Uses the canonical custom Counter initialized with "012"; an anagram-style window is valid when counter.distinct_count() == 0.

Analysis
Time
O(N)
  • Linear pass with early return optimization.
Space
O(1)
  • Counters limited by the fixed set of characters ("0", "1", "2").
FIG. SMALLEST WINDOW 012● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def smallestSubstring(self, s):
n = len(s)
left = right = 0
mini = float("inf")
counter = Counter("012")
 
hasAllChars = lambda: counter.distinct_count() == 0
 
while right < n:
# Expansion
while right < n and not hasAllChars():
counter[s[right]] -= 1
right += 1
# Shrinking
while left < right and hasAllChars():
# Logic
mini = min(mini, right - left)
counter[s[left]] += 1
left += 1
return mini if mini != float("inf") else -1

Bit Frequency Window​

3095. Shortest Subarray With OR at Least K I​

Easy·
Explanation

Same expand/shrink skeleton as the sum-based shortest-window problems, but OR isn't invertible by subtraction like a sum is - there's no way to "undo" an OR when an element leaves the window. The fix: track how many elements currently in the window have each of the 32 bits set, in bit_freq. A bit is "on" in the window's OR whenever its count is >= 1, and a bit only turns back off once its count drops to 0 - so add_freq/rem_freq can maintain the window's OR incrementally in both directions by bumping counts up on expansion and down on shrink.

Analysis
Time
O(N)
  • Each element enters and leaves the window at most once; add_freq/rem_freq/atLeastK each do fixed 32-bit work, so total work is O(32*N) = O(N).
Space
O(1)
  • bit_freq is a fixed-size array of 32 counters.
FIG. 3097 SHORTEST SUBARRAY WITH OR AT LEAST K I● INTERACTIVE
visualization loads as you reach it
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
if k == 0:
return 1
n = len(nums)
left = right = 0
or_res = 0
mini = n + 1
bit_freq = [0] * 32
 
def bin_rep(num):
bin_rep = f"{num:032b}"
for i in range(31, -1, -1):
yield (i, int(bin_rep[i]))
 
def add_freq(num):
for i, bit in bin_rep(num):
bit_freq[i] += bit
 
def rem_freq(num):
for i, bit in bin_rep(num):
bit_freq[i] -= bit
 
def atLeastK():
num = 0
for i in bit_freq:
num = num << 1 | (i >= 1)
return num >= k
 
while right < n:
while right < n and not atLeastK():
add_freq(nums[right])
right += 1
while left < right and atLeastK():
mini = min(mini, right - left)
rem_freq(nums[left])
left += 1
return mini if mini != n + 1 else -1