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)