# 3 posts tagged with "Binary Search"

View All Tags

## 424. Longest Repeating Character Replacement

``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  # lengthclass 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 resultclass 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``

## 374. Guess Number Higher or Lower

``# 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 0def 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``

## 704. Binary Search

``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``