Sunday, February 26, 2023
n
is a length of a stringn
is a length of a stringfunc characterReplacement(s string, k int) int {
if len(s) <= k {
return len(s)
}
result := 0
currentWindow := 0
right := 0
left := 0
// key = rune, value = frequency in the string
runeFrequencyMap := make(map[byte]int)
highestFrequency := 0
for right < len(s) {
currentWindow = right - left + 1
runeFrequencyMap[s[right]] += 1
// set new highest frequency
if runeFrequencyMap[s[right]] > highestFrequency {
highestFrequency = runeFrequencyMap[s[right]]
}
// make sure the rest of the characters have space
if (currentWindow - highestFrequency) > k {
currentWindow -= 1
runeFrequencyMap[s[left]] -= 1
left += 1
}
if currentWindow > result {
result = currentWindow
}
right++
}
return result
}