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

Trace Engine

Analysis

class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
left = right = 0
total = 0
mini = float("inf")
while right < n:
# Expansion
while right < n and total < target:
total += nums[right]
right += 1
# Shrinking
while left < right and total >= target:
# 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

Trace Engine

Analysis

class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
n = len(cards)
left = right = 0
counter = collections.Counter()
mini = float("inf")
 
paired = lambda: counter.get(cards[right - 1], 0) > 1
 
while right < n:
while right < n and not paired():
counter[cards[right]] += 1
right += 1
while left < right and paired():
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

Trace Engine

Analysis

class Solution:
def minWindow(self, s: str, t: str) -> str:
n = len(s)
left = right = 0
required_counter = collections.Counter(t)
counter = collections.Counter()
required = len(required_counter)
mini = (0, float("inf"))
 
contains = lambda: required == 0
req_char_satisfied = lambda i: counter[s[i]] == required_counter.get(s[i], 0)
req_char_removed = lambda i: counter[s[i]] < required_counter.get(s[i], 0)
 
while right < n:
# Expansion
while right < n and not contains():
counter[s[right]] += 1
if req_char_satisfied(right):
required -= 1
right += 1
# Shrinking
while left < right and contains():
# Logic
mini = min(mini, (left, right), key=lambda i: i[1] - i[0])
counter[s[left]] -= 1
if req_char_removed(left):
required += 1
left += 1
 
return s[slice(*mini)] if mini != (0, float("inf")) else ""

Smallest window containing 0, 1 and 2​

Smallest window containing 0, 1 and 2

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Trace Engine

Analysis

class Solution:
def smallestSubstring(self, s):
n = len(s)
left = right = 0
required_counter = {i: 1 for i in "012"}
counter = collections.Counter()
required = len(required_counter)
mini = (0, float("inf"))
 
contains = lambda: required == 0
req_char_satisfied = lambda i: counter[s[i]] == required_counter.get(s[i], 0)
req_char_removed = lambda i: counter[s[i]] < required_counter.get(s[i], 0)
 
while right < n:
# Expansion
while right < n and not contains():
counter[s[right]] += 1
if req_char_satisfied(right):
required -= 1
right += 1
# Shrinking
while left < right and contains():
# Logic
mini = min(mini, (left, right), key=lambda i: i[1] - i[0])
if mini[1] - mini[0] == 3:
return 3
counter[s[left]] -= 1
if req_char_removed(left):
required += 1
left += 1
 
return mini[1] - mini[0] if mini != (0, float("inf")) else -1