Sliding Window Technique

public class SlidingWindow {

    static int maxSumSubarray(int[] arr, int k) {
        int n = arr.length;
        if (n < k) return -1;

        int windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += arr[i];

        int maxSum = windowSum;
        for (int i = k; i < n; i++) {
            windowSum += arr[i] - arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        System.out.println("Max sum (k=3): " + maxSumSubarray(arr, 3));  // 9

        int[] arr2 = {-1, 2, 3, -4, 5, 10};
        System.out.println("Max sum (k=2): " + maxSumSubarray(arr2, 2)); // 15
    }
}

# Max sum subarray of size k � O(n) time, O(1) space
def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k: return -1

    window_sum = sum(arr[:k])  # first window
    max_sum = window_sum

    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]  # slide: add new, remove old
        max_sum = max(max_sum, window_sum)

    return max_sum

arr = [2, 1, 5, 1, 3, 2]
print("Max sum (k=3):", max_sum_subarray(arr, 3))  # 9 (5+1+3)

arr2 = [-1, 2, 3, -4, 5, 10]
print("Max sum (k=2):", max_sum_subarray(arr2, 2)) # 15 (5+10)

// Max sum subarray of size k � O(n) time, O(1) space
function maxSumSubarray(arr, k) {
    const n = arr.length;
    if (n < k) return -1;

    let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
    let maxSum = windowSum;

    for (let i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];  // slide: add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

console.log("Max sum (k=3):", maxSumSubarray([2,1,5,1,3,2], 3));   // 9
console.log("Max sum (k=2):", maxSumSubarray([-1,2,3,-4,5,10], 2)); // 15

import java.util.HashMap;

public class VariableWindow {

    static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> lastSeen = new HashMap<>();
        int maxLen = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
                left = lastSeen.get(c) + 1;
            }
            lastSeen.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    static String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>(), have = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        int formed = 0, required = need.size(), lo = 0, minLen = Integer.MAX_VALUE, start = 0;
        for (int hi = 0; hi < s.length(); hi++) {
            char c = s.charAt(hi);
            have.merge(c, 1, Integer::sum);
            if (need.containsKey(c) && have.get(c).equals(need.get(c))) formed++;
            while (formed == required) {
                if (hi - lo + 1 < minLen) { minLen = hi - lo + 1; start = lo; }
                char lc = s.charAt(lo);
                have.merge(lc, -1, Integer::sum);
                if (need.containsKey(lc) && have.get(lc) < need.get(lc)) formed--;
                lo++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));  // 3
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));     // BANC
    }
}

from collections import defaultdict

# Longest substring without repeating characters � O(n)
def length_of_longest_substring(s):
    last_seen = {}
    max_len = left = 0
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1  # shrink window
        last_seen[c] = right
        max_len = max(max_len, right - left + 1)
    return max_len

# Minimum window substring � O(n + m)
def min_window(s, t):
    need = defaultdict(int)
    for c in t: need[c] += 1
    have = defaultdict(int)
    formed = required = len(need)
    lo = min_len = float('inf')
    start = 0
    lo = 0
    for hi, c in enumerate(s):
        have[c] += 1
        if need[c] and have[c] == need[c]: formed -= 1
        while formed == 0:
            if hi - lo + 1 < min_len:
                min_len = hi - lo + 1
                start = lo
            have[s[lo]] -= 1
            if need[s[lo]] and have[s[lo]] < need[s[lo]]: formed += 1
            lo += 1
    return s[start:start + min_len] if min_len != float('inf') else ""

print(length_of_longest_substring("abcabcbb"))  # 3 ("abc")
print(length_of_longest_substring("pwwkew"))    # 3 ("wke")
print(min_window("ADOBECODEBANC", "ABC"))       # "BANC"

// Longest substring without repeating characters � O(n)
function lengthOfLongestSubstring(s) {
    const lastSeen = new Map();
    let maxLen = 0, left = 0;
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        if (lastSeen.has(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;  // shrink window
        }
        lastSeen.set(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

// Minimum window substring � O(n + m)
function minWindow(s, t) {
    const need = new Map(), have = new Map();
    for (const c of t) need.set(c, (need.get(c) || 0) + 1);
    let formed = 0, required = need.size;
    let lo = 0, minLen = Infinity, start = 0;
    for (let hi = 0; hi < s.length; hi++) {
        const c = s[hi];
        have.set(c, (have.get(c) || 0) + 1);
        if (need.has(c) && have.get(c) === need.get(c)) formed++;
        while (formed === required) {
            if (hi - lo + 1 < minLen) { minLen = hi - lo + 1; start = lo; }
            const lc = s[lo];
            have.set(lc, have.get(lc) - 1);
            if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
            lo++;
        }
    }
    return minLen === Infinity ? "" : s.slice(start, start + minLen);
}

console.log(lengthOfLongestSubstring("abcabcbb"));  // 3
console.log(minWindow("ADOBECODEBANC", "ABC"));     // "BANC"