Skip to main content

3 posts tagged with "String"

View All Tags

class Solution:
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271
def characterReplacement(self, s: str, k: int) -> int:
c, mf = {}, 0 # counter, max_freq
l, N = 0, len(s)
for r in range(N):
c[s[r]] = c.get(s[r], 0) + 1
mf = max(mf, c[s[r]])
if not ((r + 1) - l - mf <= k): # shift right
c[s[l]] -= 1
l += 1
# find next if same
return N - l # length


class Solution2:
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271
def characterReplacement(self, s: str, k: int) -> int:
result = 0
c, mf = {}, 0 # counter, max_freq
for r in range(len(s)):
c[s[r]] = c.get(s[r], 0) + 1
mf = max(mf, c[s[r]])
if result - mf >= k:
c[s[r - result]] -= 1
else:
result += 1 # update when more
return result


class SolutionBS: # 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 = {}, 0
l = 0
for r in range(len(s)):
c[s[r]] = c.get(s[r], 0) + 1
if r + 1 - l > length:
c[s[l]] -= 1
l += 1
mf = max(mf, c[s[r]])
if length - mf <= k:
return False
return True

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