Sliding window: Longest repeating character or substring with replacements Python
Thu Sep 22 2022 03:51:20 GMT+0000 (Coordinated Universal Time)
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
else:
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
content_copyCOPY
Time: O(N)
Space: O(1) because we know it cannot be more than 26 letters in frequency dictionary
https://leetcode.com/problems/longest-repeating-character-replacement/
Comments