Sliding Window Questions Part 1
146. (LC 567) Permutation in String
567. Permutation in String Medium
-we make hash tables using collections.Counter()
Of the full s1.
Of the part of s2, window size, which is len of s1.
-we can compare dicts!
if cnt1 == cnt2:
-Move the window. Iterate starting from len(s1).
(Modify hash tables. Simply +=1 to the value at rp, -= to the key in hash at lp)
from collections import Counter
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
n = len(s1)
cnt1 = Counter(s1)
cnt2 = Counter(s2[:n])
if cnt1 == cnt2:
return True
for i in range(n, len(s2)):
cnt2[s2[i]] += 1
cnt2[s2[i - n]] -= 1
if cnt1 == cnt2:
return True
return False
### My remake
def f(s1, s2):
if len(s1) > len(s2):
return False
cnts1 = collections.Counter(s1)
cnts2 = collections.Counter(s2[: len(s1)])
if cnts1 == cnts2:
return True
lp = 0
for rp in range(len(s1), len(s2)):
cnts2[s2[rp]] += 1
cnts2[s2[lp]] -= 1
lp += 1
if cnts1 == cnts2:
return True
return False
Note
we use special properties of dicts, created by collections.Counter(iterable)
1)
cnts2[s2[rp]] += 1
Counter makes a dict with properties like defaultdict. So we can add to non-existent keys,
which doesn’t work in a regular dict.
>>> import collections
>>> s='abc'
>>> cnt=collections.Counter(s)
>>> cnt['f']+=1 #'f' is not in cnt, but we add to it OK
>>> cnt
Counter({'a': 1, 'b': 1, 'c': 1, 'f': 1})
>>> d={'b':1}
>>> d['c']+=1 #Nope in reg dict
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'c'
2)
if cnts1 == cnts2:cnts like cnt1={‘a’:1, ‘d’:0}, cnt2={‘a’:1} will be equal,
again which is not the case for normal dict.
Solution 2 (If you don’t want to use Python tricks.) [10]
-What is your sliding window going to be?
The size of your window in s2 (longer string) is the len of s1 (shorter string).
We will have 2 hash maps: for chars in s1 and those in s2.
Arrays are used here: [0]*26
In each hash/array we will be tracking the counts for all 26 chars.
No char in string will have count 0, char present, count=1
Variable matches=0
E.g.
s1=’abc’, s2=’baxyzabc’
window 1 = ‘bax’
matches=24
window 2 = ‘axy’
matches=22
..Stop when we have matches=26
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1Count, s2Count = [0] * 26, [0] * 26
for i in range(len(s1)):
s1Count[ord(s1[i]) - ord("a")] += 1 #fills in hash/array for s1
s2Count[ord(s2[i]) - ord("a")] += 1 #fills in for window1 of s2
matches = 0
for i in range(26): #matches for window1,yes iterate through all 26 values
matches += 1 if s1Count[i] == s2Count[i] else 0
l = 0
for r in range(len(s1), len(s2)): #<==Move RP
if matches == 26:
return True
index = ord(s2[r]) - ord("a") #BLOCK 1 for rp
s2Count[index] += 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] + 1 == s2Count[index]: #if in s1 'a'=0, in s2 'a'=1
matches -= 1
index = ord(s2[l]) - ord("a") #BLOCK 2 for lp
s2Count[index] -= 1
if s1Count[index] == s2Count[index]:
matches += 1
elif s1Count[index] - 1 == s2Count[index]: #if in s1 we had 'a'=1, now in s2 'a'=0
matches -= 1
l += 1 #<==Move LP
return matches == 26
### My V (LC accepted 78,84%)
def f(s1, s2):
d = {}
for c in s1:
d[c] = 1 + d.get(c, 0)
total_cnt = sum([v for v in d.values()])
lp = rp = 0
# for rp in range(len(s2)): NOPE
while rp < len(s2):
if s2[rp] in d and d[s2[rp]] > 0:
d[s2[rp]] -= 1
total_cnt -= 1
if total_cnt == 0:
return True
else:
if s2[rp] not in d: #s2[rp] not in D, build from scratch
while lp != rp:
d[s2[lp]] += 1
lp += 1
total_cnt += 1
else: #s2[rp] in D, don't build from scratch, just try moving lp
d[s2[lp]] += 1
total_cnt += 1
rp -= 1 #Move rp BACK and try again
lp += 1
rp += 1 #DONT FORGET
return False
Seems to be a classic sliding window.
One tricky edge case:
s1 = “adc”
s2 = “dcda” #True has s1 substring
# d c d a
# L R
Case 1) value at R in hash and D[s2[R]]> 0, so L stays, R +=1
Case 2) value at R not in hash, just move L all the way to R (L=R), start looking from scratch.
-> spec. case 3) value at R in hash, but D[s2[R]]=0.
Then L+1, R-1 and try again.
147 (LC 239) Sliding Window Maximum
239. Sliding Window Maximum Hard
The example given in the task is misleading (makes you think that mono increasing stack is enough).
A better one that covers more cases:
nums = [0, 5, 3, 2, 1, 2, 4, 4]
Keys
-use dequeue, mono decreasing, store (value, index)
E.g.: q = [(5,1), (3,2), (2,3)] (so the greatest value is always at q[0])
-pop from dequeue if current value greater than previous values, q[-1]
cur=2, q=[(2,3), (1,4)], pop val=1 => q=[(2,3), [2,5]]
-popleft if index of the value on the left of q (q[0] i.e. greatest) is beyond our k window
cur i = 4, q = [(5,1), (3,2), (2,3)], pop (5,1)
-append to ans value at q[0], first value in q is always the greatest.
QUEUE (my V):
### My V (LC accepted 30, 50)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans = []
q = collections.deque()
for i, n in enumerate(nums):
while q and q[-1][0] < n:
q.pop()
while q and q[0][1] <= i-k:
q.popleft()
q.append((n, i))
if i >= k-1:
ans.append(q[0][0])
return ans
HEAP
-Using min heap, store (value, index) pairs.
Because we may have a situation like this:
nums = [9,10,9,-7,-4,-8,2,-6]
k = 5
Storing just values in heap, would give output: [10,10,9,9] instead of [10,10,9,2].
(We never deleted 2nd to greatest (9) that we’ve passed.)
To delete all values that we’ve passed, store also indices in heap.
### My V (LC accepted 10, 5)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = [(-n, i) for i, n in enumerate(nums[:k-1])]
heapq.heapify(q)
ans = []
for i in range(k-1, len(nums)):
heapq.heappush(q, (-nums[i], i))
lp = i+1-k
while q[0][1] < lp:
heapq.heappop(q)
ans.append(-q[0][0])
return ans
Solution 2 [7]:
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = [(-v, i) for i, v in enumerate(nums[: k - 1])]
heapify(q)
ans = []
for i in range(k - 1, len(nums)):
heappush(q, (-nums[i], i))
while q[0][1] <= i - k:
heappop(q)
ans.append(-q[0][0])
return ans
148 (LC 904) Fruit Into Baskets
LC 904. Fruit Into Baskets Medium
Keys
-note, 2 kinds of fruit, so when dict has more than 2 keys: collect result, pop from
dict value at lp.
-Thanks to defaultdict(int), we can add value at rp to dict every time without testing
for presence.
-Then subtract values at key a[lp], when d[a[lp]]==0, just pop it entirely from the dict.
Solution 1 [10] LC accepted
import collections
def f(a):
d = collections.defaultdict(int)
lp = 0
cur_len = 0
max_len = 0
for rp in range(len(a)):
d[a[rp]] += 1
cur_len += 1
while len(d) > 2:
value = a[lp]
d[value] -= 1
cur_len -= 1
lp += 1
if d[value] == 0:
d.pop(value)
max_len = max(max_len, cur_len)
return max_len
149 (LC 1456) Maximum Number of Vowels in a Substring of Given Length
1456. Maximum Number of Vowels in a Substring of Given Length Medium
# My V (LC accepted 75,90%)
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = {'a': 1, 'e': 1, 'i': 1, 'o':1, 'u':1}
L, cnt, cnt_cur = 0,0,0
for R in range(len(s)):
if s[R] in vowels:
cnt_cur+=1
cnt = max(cnt, cnt_cur)
if (R-L+1) == k:
if s[L] in vowels:
cnt_cur -=1
L+=1
return cnt
Solution 1 [10]
class Solution:
def maxVowels(self, s: str, k: int) -> int:
l, res, total = 0, 0, 0
vowels = "aeiou"
for r in range(len(s)):
if s[r] in vowels:
total += 1
if (r - l + 1) > k:
if s[l] in vowels:
total -= 1
l += 1
res = max(res, total)
return res
150. (LC 1004) Max Consecutive Ones III
1004. Max Consecutive Ones III Medium
Keys
-Sliding window.
-When p2 is at the last item, be it 0 or 1, flips being == to k or not, calculate max_len always.
(Also note that then len=p2-p1+1.)
### My V2 (LC accepted 72,93%)
def max_consequtive_ones(nums, k):
p1 = p2 = 0
max_len = 0
flips = 0
for p2 in range(len(nums)):
if nums[p2] == 0:
if flips < k:
flips += 1
elif flips == k:
max_len = max(max_len, p2 - p1)
# flips+=1
while nums[p1] == 1:
p1 += 1
p1 += 1
# flips -= 1
if p2 == len(nums) - 1: #important to have IF here not elif, when k is very large
max_len = max(max_len, p2 - p1 + 1) # p2 - p1 + 1
return max_len
Solution 1 [7]
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
ans = 0
cnt = j = 0
for i, v in enumerate(nums):
if v == 0:
cnt += 1
while cnt > k:
if nums[j] == 0:
cnt -= 1
j += 1
ans = max(ans, i - j + 1)
return ans
151. (LC 1493) Longest Subarray of 1’s After Deleting One Element
1493. Longest Subarray of 1’s After Deleting One Element Medium
My note:
it’s not that you are allowed to delete one element, you must, even if it is a 1.
Solution 1
(Recording zi, index at which we encounter 0 each time. To then move the lp there.)
def f(a):
lp, ans, zi = 0, 0, -1
for rp in range(len(a)):
if a[rp] == 0:
lp = zi + 1
zi = rp
ans = max(ans, rp - lp) #**
return ans
#**calculate here to take care of all the edge cases:
-array ends with 1s,
-there are no 0s in array.
nums = [0, 1, 1, 1, 0, 1, 1, 0, 1] #5
nums = [0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1] #6
nums = [1, 1, 1] #2
print(f(nums))
Solution 2
(Keep a count of how many zeros we encountered. When cnt > 1, shrink the window, i.e. move lp till cnt is again == 1. Because we can have one 0 in the window.)
def f(a):
lp, ans, zcnt = 0, 0, 0
for rp in range(len(a)):
if a[rp] == 0:
zcnt += 1
while zcnt > 1:
if a[lp] == 0:
zcnt -= 1
lp += 1
ans = max(ans, rp - lp)
return ans