Open
Description
'''
start[6:12]
Problem Solving:
[?] Sliding window algorithm
* Potentially scan through with 2 pointers
- left being the window shrinker
- right being the window extender
extend right point until meeting the condition of S contains all T
take GlobalMin
then shrink the size of left
2 pointer algorithm takes O(N), not sure yet for checking S contains all T part, I am a bit stuck here.
Stuck:
One way to verify Target in S, is the making a set of every window
but that takes O(len(window)) time complexity for convertion
Can we make a dictionary of S before hand
"ADOBECODEBANC"
{
char : count
A : 1
}
I can think of a way in which having Target becomes a hashset
Having a fixed hashtable to store S's state initially
Having a second hashtable to change count frequency
If visted, count of associated element decrement by 1
Each time, for loop -> Target hashset:
then find comparision of inital hashtable & frequently changed hastable to get the diff
If diff more than 1 for every element in hashset
Meet the condition
Time Complexity:
O(N) + O(size of Target)
[6:26] Ok, having brainfart , solution time?
[7:06] Done, need to re-do
'''
from collections import Counter
class Solution:
def minWindow(self, nums , target):
if nums is None: return ""
targetHash = Counter(target)
curHash = {}
targetCount = len(targetHash)
matched = 0
globalMin = float("inf")
size = len(nums)
res = ""
j = 0
for i in range(size):
# 不断增大窗口大小,知道满足所有Match需求
while j < size and matched < targetCount:
if nums[j] in targetHash:
curHash[nums[j]] = curHash.get(nums[j], 0) + 1
if curHash[nums[j]] == targetHash[nums[j]]:
matched += 1
j += 1
# 更新最小值
if j - i < globalMin and matched == targetCount:
globalMin = j - i
res = nums[i:j]
# 删除left的一个元素,使得窗口继续滑动
if nums[i] in targetHash:
if curHash[nums[i]] == targetHash[nums[i]]:
matched -= 1
curHash[nums[i]] -= 1
return res
Metadata
Metadata
Assignees
Labels
No labels