Скользящее окно для подстрок

Концепция скользящего окна

# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
    window_sum = sum(nums[:k])  # initial window
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i]       # add new right
        window_sum -= nums[i - k]   # remove old left
        best = max(best, window_sum)
    return best

print(max_sum_window([2,1,5,1,3,2], 3))  # 9  ([5,1,3])

Фиксированный и переменный размер окна

# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
    from collections import defaultdict
    freq = defaultdict(int)
    left = 0
    best = 0
    for right in range(len(s)):
        freq[s[right]] += 1
        while len(freq) > k:    # window invalid: shrink
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_k_distinct('eceba', 2))   # 3  ('ece')
print(longest_k_distinct('aa', 1))      # 2

Самая длинная подстрока без повторений

def length_of_longest_substring(s):
    char_idx = {}  # char -> last seen index
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in char_idx and char_idx[c] >= left:
            left = char_idx[c] + 1  # jump past duplicate
        char_idx[c] = right
        best = max(best, right - left + 1)
    return best

print(length_of_longest_substring('abcabcbb'))  # 3 ('abc')
print(length_of_longest_substring('bbbbb'))     # 1
print(length_of_longest_substring('pwwkew'))    # 3 ('wke')

Минимальная подстрока

from collections import Counter

def min_window(s, t):
    if not t or not s: return ''
    need = Counter(t)
    have = {}
    formed = 0
    required = len(need)
    left = 0
    best = float('inf'), 0, 0
    for right, c in enumerate(s):
        have[c] = have.get(c, 0) + 1
        if c in need and have[c] == need[c]:
            formed += 1
        while formed == required:
            if right - left + 1 < best[0]:
                best = right - left + 1, left, right
            have[s[left]] -= 1
            if s[left] in need and have[s[left]] < need[s[left]]:
                formed -= 1
            left += 1
    return s[best[1]:best[2]+1] if best[0] != float('inf') else ''

print(min_window('ADOBECODEBANC', 'ABC'))  # 'BANC'

Шаблон скользящего окна

def sliding_window_template(s, condition_check, update_state, remove_state):
    """
    Generic sliding window skeleton.
    Adapt condition_check, update_state, remove_state per problem.
    """
    left = 0
    state = {}  # or whatever state you need
    best = 0
    for right in range(len(s)):
        update_state(state, s[right])      # expand window
        while not condition_check(state):  # window invalid
            remove_state(state, s[left])   # shrink window
            left += 1
        best = max(best, right - left + 1)
    return best

Перестановка в строке

from collections import Counter

def check_inclusion(p, s):
    if len(p) > len(s): return False
    need  = Counter(p)
    window = Counter(s[:len(p)])
    if need == window: return True
    for right in range(len(p), len(s)):
        left = right - len(p)
        window[s[right]] += 1
        window[s[left]]  -= 1
        if window[s[left]] == 0:
            del window[s[left]]
        if window == need:
            return True
    return False

print(check_inclusion('ab', 'eidbaooo'))  # True ('ba')
print(check_inclusion('ab', 'eidboaoo'))  # False

Подстроки-анаграммы: подсчёт всех

from collections import Counter

def find_anagrams(s, p):
    result = []
    need = Counter(p)
    k = len(p)
    window = Counter(s[:k])
    if window == need:
        result.append(0)
    for right in range(k, len(s)):
        window[s[right]] += 1
        left_char = s[right - k]
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]
        if window == need:
            result.append(right - k + 1)
    return result

print(find_anagrams('cbaebabacd', 'abc'))  # [0, 6]

Самая длинная подстрока не более чем с 2 различными символами

def longest_substring_two_distinct(s):
    from collections import defaultdict
    freq = defaultdict(int)
    left = 0
    best = 0
    for right, c in enumerate(s):
        freq[c] += 1
        while len(freq) > 2:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_substring_two_distinct('eceba'))     # 3  ('ece')
print(longest_substring_two_distinct('ccaabbb'))   # 5  ('aabbb')

Максимум в скользящем окне

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, decreasing values
    result = []
    for i, n in enumerate(nums):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order
        while dq and nums[dq[-1]] < n:
            dq.pop()
        dq.append(i)
        if i >= k - 1:  # window is full
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

Когда использовать скользящее окно

# Recognising sliding window problems:

# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
    s = sum(nums[:k])
    best = s
    for i in range(k, len(nums)):
        s += nums[i] - nums[i-k]
        best = max(best, s)
    return best / k

print(max_avg([1,12,-5,-6,50,3], 4))  # 12.75

# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
    left = s = 0
    best = float('inf')
    for right, n in enumerate(nums):
        s += n
        while s >= target:
            best = min(best, right - left + 1)
            s -= nums[left]; left += 1
    return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3]))  # 2

Подсчёт допустимых окон: не более K

from collections import defaultdict

def subarrays_at_most_k(s, k):
    freq = defaultdict(int)
    left = 0
    count = 0
    for right, c in enumerate(s):
        freq[c] += 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0: del freq[s[left]]
            left += 1
        count += right - left + 1  # all valid windows ending at right
    return count

def subarrays_exactly_k(s, k):
    return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)

print(subarrays_exactly_k('araaci', 2))  # 9

Быстрая проверка

Итоги урока