Skip to main content

4 posts tagged with "Sliding Window"

View All Tags

· One min read
class Solution1:
def lengthOfLongestSubstring(self, s: str) -> int:
result, chars = 0, set()
for j, c in enumerate(s):
while c in chars:
i = j - len(chars)
chars.remove(s[i])
chars.add(c)
result = max(result, len(chars))
return result


class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
result, i, chars = 0, 0, {}
for j, char in enumerate(s):
i = max(i, chars.get(char, -1) + 1)
chars[char] = j
result = max(result, j - i + 1)
return result

· One min read
class Solution:  # O(n) / O(n)
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
def characterReplacement(self, s: str, k: int) -> int:
c = {} # counter
mf = 0 # max_freq
i = 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if not ((j - i + 1) - mf <= k): # shift right
c[s[i]] -= 1
i += 1
return len(s) - i # length


class Solution2: # O(n) / O(n)
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
def characterReplacement(self, s: str, k: int) -> int:
c = {}
mf, i = 0, 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if i - mf >= k:
c[s[j - i]] -= 1
else:
i += 1 # update when more
return i


class SolutionBS: # O(log(n)) / O(n)
# TODO: review
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/2805777
def characterReplacement(self, s: str, k: int) -> int:
def too_long(length: int):
c = {}
mf, i = 0, 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if length - mf <= k:
return False
if j - i + 1 > length:
c[s[i]] -= 1
i += 1
return True

l, r = 0, len(s)
while l < r:
m = (l + r) // 2
l, r = (l, m) if too_long(length=m + 1) else (m + 1, r)
return (l - 1) + 1