Skip to main content

Shortest Sub{string,array}

Usually, both expansion and shrinking will be having while loop, and condition for shrink will just be the complement/negation/opposite of expansion.

Naive​

while expand + while shrink

209. Minimum Size Subarray Sum​

209. Minimum Size Subarray Sum

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

while expand + while shrink

76. Minimum Window Substring​

76. Minimum Window Substring

Hard1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Smallest window containing 0, 1 and 2

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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