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​

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·
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·
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·
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·
FIG. 3095 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