4 posts tagged with "Sliding Window"

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

class Solution:
    def countCompleteSubarrays(self, nums: list[int]) -> int:
        amt, D, result, i = {}, len(set(nums)), 0, 0
        for num in nums:
            amt[num] = amt.get(num, 0) + 1
            while len(amt) == D:
                amt[nums[i]] -= 1
                if amt[nums[i]] == 0:
                    del amt[nums[i]]
                i += 1
            result += i
        return result

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

from collections import Counter


class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        result, s, P = [], s + ' ', len(p)
        cp, cs = Counter(p), Counter(s[:P])
        for i in range(len(s) - P):
            if cp == cs:
                result.append(i)
            cs.subtract(s[i])
            cs.update(s[i + P])
        return result