Sliding window: Longest subarray with ones after replacement Python
Mon Sep 26 2022 16:11:18 GMT+0000 (Coordinated Universal Time)
Saved by
@bryantirawan
#python
#hashmap
#grokking
def length_of_longest_substring(arr, k):
#set start, maxLength, maxRepeat
start, maxLength, maxRepeat = 0, 0, 0
#set frequencyDict
frequencyDict = {}
#iterate through arr
for end in range(len(arr)):
#add to frequencyDict
right = arr[end]
if right not in frequencyDict:
frequencyDict[right] = 1
else:
frequencyDict[right] += 1
#find maxRepeat
maxRepeat = max(maxRepeat, frequencyDict[right])
#evaluate window
if (end - start + 1 - maxRepeat) > k:
#reduce window by 1 and adjust frequency map
left = arr[start]
frequencyDict[left] -= 1
start += 1
#check maxLength
maxLength = max(maxLength, end - start + 1)
return maxLength
length_of_longest_substring([0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], 3)
content_copyCOPY
Time: O(N)
Space: O(2) >> O(1)
Comments