Skip to main content

3 posts tagged with "Binary Search"

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

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
# 1 if num is lower than the picked number
# otherwise return 0
def guess(num: int) -> int:
...


class Solution:
def guessNumber(self, n: int) -> int:
l, r = 0, n
while l < r:
m = (l + r) // 2
if not guess(m):
return m
l, r = (l, m) if guess(m) < 0 else (m + 1, r)
return l

class Solution:
def search(self, nums: list[int], target: int) -> int:
l, r = 0, len(nums)
while l < r:
m = (l + r) // 2
if nums[m] == target:
return m
l, r = (l, m) if nums[m] > target else (m + 1, r)
return -1