Sliding_Window_Problems.py

# 1. Fixed Window Size Problem
# Problem: Maximum Sum of Subarray of Size k
# Given an array of integers and a fixed window size k, find the maximum sum of any subarray of length k.

def size_of_max_sum(arr: list, k: int) -> int:
    
    max_sum = curr_sum = sum(arr[:k])
    
    for i in range(k, len(arr)):
        curr_sum = curr_sum + arr[i] - arr[i -k]
        if curr_sum > max_sum:
            max_sum = curr_sum
            
    return max_sum

# 2. Variable Window Size Problem
# Problem: Smallest Subarray with Sum ≥ target
# Given an array of positive integers and a target sum, find the length of the smallest contiguous subarray whose sum is ≥ target.

def smallest_subarray_with_sum(arr: list, target: int) -> int:
    
    min_len = float('inf')
    curr_sum = 0
    left = 0
    
    for right in range(len(arr)):
        curr_sum += arr[right]
        
        while curr_sum >= target:
            min_len = min(min_len, right - left + 1)
            curr_sum -= arr[left]
            left += 1
            
    return min_len if min_len != float('inf') else 0

# 1. Fixed Window Size Problem
# Problem: Count Occurrences of Anagrams
# Given a string s and a pattern p, find how many anagrams of p exist in s as contiguous substrings.

def count_occurrences_anagrams(s: str, p: str) -> int:
    
    k = len(p)
    
    if len(s) < k:
        return 0
    count = 0
    p_sorted = sorted(p)
    
    for i in range(len(s) - k + 1):
        
        mystr = s[i:i+k]
        
        if sorted(mystr) == p_sorted:
            count += 1
          
    return count

from collections import defaultdict
def count_occurrences_anagrams_fixed_window(s: str, p: str) -> int:
    
    k = len(p)
    
    if len(s) < k:
        return 0
    
    p_count = defaultdict(int)
    word_count = defaultdict(int)
    
    for char in p:
        p_count[char] += 1
        
    for char in s[:k]:
        word_count[char] += 1
        
    count = 1 if word_count == p_count else 0
    
    for i in range(k, len(s)):
        
        old_char = s[i - k]
        
        if word_count[old_char] == 1:
            del word_count[old_char]
        else:
            word_count[old_char] -= 1
            
        new_char = s[i]
        word_count[new_char] += 1
        
        if word_count == p_count:
            count += 1
    return count
        
        
# 2. Variable Window Size Problem
# Problem: Longest Substring Without Repeating Characters
# Given a string s, find the length of the longest substring without repeating characters.

def longest_substring_without_repeating(s: str) -> int:
    
    char_index = {}
    max_length = 0
    left = 0
    
    for right in range(len(s)):
        if s[right] in char_index:
            left = max(left, char_index[s[right]] + 1)
        
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)
        
    return max_length

s = "abcabcbb" 

print(longest_substring_without_repeating(s))