Sliding window: Longest repeating character or substring with replacements Python


Thu Sep 22 2022 03:51:20 GMT+0000 (UTC)

Saved by @bryantirawan #python #neetcode

def length_of_longest_substring(str1, k):
    window_start, max_length, max_repeat_letter_count = 0, 0, 0 
    frequency_map = {} 
    #try to extend window [window_start, window_end] 
    for window_end in range(len(str1)): 
        right_char = str1[window_end]
        if right_char not in frequency_map: 
            frequency_map[right_char] = 1 
            frequency_map[right_char] += 1 
        #we don't need to place the maxRepeatLetterCount under the below 'if'
        #while shrinking window, we don't need to update maxRepeatLetterCount 
        #since we are only interested in longest valid substring, our sliding windows do not have to shrink even if a window may cover an invalid substring 
        max_repeat_letter_count = max(max_repeat_letter_count, frequency_map[right_char]) 
        #determine if window is still valid 
        #if remaining letters are more than k, it is time to shrink window as we are not allowed to replace more than k letters 
        evaluate_window = window_end - window_start + 1 - max_repeat_letter_count
        if evaluate_window > k: 
            left_char = str1[window_start] 
            frequency_map[left_char] -= 1 
            window_start += 1 
        max_length = max(max_length, window_end - window_start + 1) 
    return max_length 

length_of_longest_substring("aabccbb", 2)

#alternate solution 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        result = 0 
        left = 0 
        for right in range(len(s)): 
            #add s[right] to count dictionary 
            count[s[right]] = 1 + count.get(s[right], 0) #if s[right] does not exist in count hashmap, then set default value to 0 
            #make sure current window is valid 
            #while (windowLength - length of most frequent char in count hashmap) > k 
            while (right - left + 1) - max(count.values()) > k: #this statement means window is no longer valid 
                #need to remove one from s[left] 
                count[s[left]] -= 1 
                left += 1 
            result = max(result, right - left + 1)
        return result 

Time: O(N) Space: O(1) because we know it cannot be more than 26 letters in frequency dictionary