Sliding Window

1def max_sum_subarray(nums, k):
2    if len(nums) < k: return 0  # WHY guard? Can't form a window of size k
3    window_sum = sum(nums[:k])  # Build the first window: O(k) one-time cost
4    max_sum = window_sum        # First window might be the answer
5
6    for i in range(k, len(nums)):
7        # WHY +nums[i] - nums[i-k]? nums[i] enters the window,
8        # nums[i-k] leaves it. Net change in sum — O(1) per slide.
9        window_sum += nums[i] - nums[i - k]
10        max_sum = max(max_sum, window_sum)
11    return max_sum  # O(n) time, O(1) space

1def length_of_longest_substring(s):
2    char_index = {}  # WHY map not set? We store the INDEX, not just presence.
3                     # This lets us jump left directly instead of sliding 1-by-1.
4    left, best = 0, 0
5
6    for right in range(len(s)):
7        # WHY check >= left? The char might have been seen before, but if its
8        # last index is BEFORE our window (< left), it is not a duplicate in
9        # the current window. We only care about duplicates inside [left, right].
10        if s[right] in char_index and char_index[s[right]] >= left:
11            left = char_index[s[right]] + 1  # WHY +1? Jump PAST the duplicate
12        char_index[s[right]] = right  # Always update to latest index
13        best = max(best, right - left + 1)  # Window [left..right] is valid
14    return best  # O(n) time, O(min(n, 26)) space

1from collections import Counter
2
3def min_window(s, t):
4    if not t or not s:
5        return ""
6    need = Counter(t)          # What we need: char -> required count
7    have = {}                  # What we have: char -> current count in window
8    need_cnt, have_cnt = len(need), 0  # WHY len(need)? Count UNIQUE chars needed
9    left, best = 0, (float('inf'), 0, 0)
10
11    for right in range(len(s)):
12        ch = s[right]
13        have[ch] = have.get(ch, 0) + 1  # Add char to our window
14
15        # WHY == not >=? We only increment have_cnt at the exact moment
16        # a character reaches its required frequency. If we used >=, we
17        # would count it multiple times as more duplicates arrive.
18        if ch in need and have[ch] == need[ch]:
19            have_cnt += 1
20
21        # SHRINK: when all required chars are satisfied, try to minimize
22        while have_cnt == need_cnt:
23            if right - left + 1 < best[0]:
24                best = (right - left + 1, left, right)
25            out = s[left]
26            have[out] -= 1
27            # WHY check < need[out]? We just dropped below the required
28            # count for this character — the window is no longer valid
29            if out in need and have[out] < need[out]:
30                have_cnt -= 1
31            left += 1
32
33    return s[best[1]:best[2]+1] if best[0] != float('inf') else ""
34# Time: O(|s| + |t|)  Space: O(|s| + |t|)

1def check_inclusion(s1, s2):
2    if len(s1) > len(s2):
3        return False
4    s1_count, win_count = {}, {}
5    for ch in s1:
6        s1_count[ch] = s1_count.get(ch, 0) + 1  # Frequency map of target
7    k = len(s1)  # WHY fixed size k? A permutation has the same length
8
9    for i in range(len(s2)):
10        ch = s2[i]
11        win_count[ch] = win_count.get(ch, 0) + 1  # Add incoming char
12
13        if i >= k:  # WHY i >= k? Once we have more than k chars, remove the oldest
14            left_ch = s2[i - k]
15            win_count[left_ch] -= 1
16            if win_count[left_ch] == 0:
17                del win_count[left_ch]  # WHY delete? So map equality works correctly
18
19        # WHY direct map comparison? Two maps are equal iff they have the same
20        # keys with the same values — exactly the definition of "same frequencies"
21        if win_count == s1_count:
22            return True
23    return False
24# Time: O(n), Space: O(1) -- at most 26 keys

1def total_fruit(fruits):
2    count = {}          # fruit_type -> frequency in window
3    left = 0
4    best = 0
5
6    for right in range(len(fruits)):
7        # EXPAND: add the new fruit to our basket
8        f = fruits[right]
9        count[f] = count.get(f, 0) + 1
10
11        # SHRINK: if we have more than 2 types, remove from left
12        while len(count) > 2:
13            left_f = fruits[left]
14            count[left_f] -= 1
15            if count[left_f] == 0:
16                del count[left_f]  # Critical: remove empty types
17            left += 1
18
19        # UPDATE: window is valid (at most 2 types), track max length
20        best = max(best, right - left + 1)
21
22    return best
23# O(n) time, O(1) space (at most 3 keys in map)