Sliding Window Technique — Fixed Window, Variable Window, Patterns & Production Pitfalls

package io.thecodeforge.algo;

public class MaxSumSubarrayFixedWindow {

    /**
     * Finds the maximum sum of any contiguous subarray of size k.
     * Fixed-size sliding window — O(n) time, O(1) space.
     */
    public static int maxSumSubarray(int[] arr, int k) {
        if (arr.length < k) {
            throw new IllegalArgumentException("Array length must be >= k");
        }

        // Compute sum of first window
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        int maxSum = windowSum;

        // Slide the window: add right element, remove left element
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i];      // add incoming element at right edge
            windowSum -= arr[i - k];  // remove outgoing element at left edge
            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 — [5,1,3]
        System.out.println("Max sum (k=2): " + maxSumSubarray(arr, 2));  // 6 — [5,1]
        System.out.println("Max sum (k=4): " + maxSumSubarray(arr, 4));  // 10 — [5,1,3,2]

        // Trace the window slides for k=3:
        // [2,1,5] sum=8  max=8
        // [1,5,1] sum=7  max=8  (removed 2, added 1)
        // [5,1,3] sum=9  max=9  (removed 1, added 3)
        // [1,3,2] sum=6  max=9  (removed 5, added 2)
    }
}

package io.thecodeforge.algo;

/**
 * Summary of the two sliding window flavors.
 * Both achieve O(n) by visiting each element at most twice.
 */
public class SlidingWindowPatternSummary {

    /*
     * FIXED-SIZE WINDOW
     * ─────────────────
     * Setup: compute sum/state of first k elements.
     * Slide: add arr[right], subtract arr[right-k]. Update result.
     * Constraint: window size is always exactly k.
     * Time: O(n), Space: O(1)
     * Examples: max sum subarray of size k, moving average, max of all subarrays of size k.
     */

    /*
     * VARIABLE-SIZE WINDOW
     * ────────────────────
     * Setup: left=0, right=0, empty state.
     * Expand: advance right, add arr[right] to state.
     * Shrink: while constraint violated, remove arr[left], advance left.
     * Constraint: dynamically maintained (distinct count, sum threshold, etc.)
     * Time: O(n), Space: O(k) where k is constraint size
     * Examples: longest substring without repeating, min window substring, longest subarray with sum <= target.
     */

    public static void main(String[] args) {
        System.out.println("Sliding Window Flavors:");
        System.out.println("1. Fixed-size   — window is always k elements. Add right, subtract left.");
        System.out.println("2. Variable-size — expand right, shrink left when constraint violated.");
        System.out.println("\nBoth: each element enters and exits at most once. O(n) total.");
    }
}

package io.thecodeforge.algo;

public class MaxSumSubarrayFixedWindow {

    public static int maxSumSubarray(int[] arr, int k) {
        if (arr.length < k) {
            throw new IllegalArgumentException("Array length must be >= k");
        }

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

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

        return maxSum;
    }

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

package io.thecodeforge.algo;

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    /**
     * Finds the longest substring with no repeating characters.
     * Variable-size sliding window with HashMap tracking last-seen index.
     * O(n) time, O(min(n, alphabet)) space.
     */
    public static String longestNonRepeating(String text) {
        Map<Character, Integer> lastSeenAtIndex = new HashMap<>();
        int maxLength = 0;
        int windowStart = 0;
        int bestWindowStart = 0;

        for (int windowEnd = 0; windowEnd < text.length(); windowEnd++) {
            char currentChar = charAt(windowEnd, text);

            // If char was seen AND is inside current window, shrink left past it
            if (lastSeenAtIndex.containsKey(currentChar)
                    && lastSeenAtIndex.get(currentChar) >= windowStart) {
                windowStart = lastSeenAtIndex.get(currentChar) + 1;
            }

            lastSeenAtIndex.put(currentChar, windowEnd);

            int currentLength = windowEnd - windowStart + 1;
            if (currentLength > maxLength) {
                maxLength = currentLength;
                bestWindowStart = windowStart;
            }
        }

        return text.substring(bestWindowStart, bestWindowStart + maxLength);
    }

    private static char charAt(int index, String text) {
        return text.charAt(index);
    }

    public static void main(String[] args) {
        String[] tests = {"abcabcbb", "bbbbb", "pwwkew", "thecodeforge"};
        for (String input : tests) {
            String result = longestNonRepeating(input);
            System.out.printf("Input: %-15s → \"%s\" (length %d)%n",
                              "\"" + input + "\"", result, result.length());
        }
    }
}

package io.thecodeforge.algo;

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringKDistinct {

    /**
     * Finds the longest substring with at most k distinct characters.
     * Variable-size sliding window with frequency map.
     * O(n) time, O(k) space.
     */
    public static int longestSubstringKDistinct(String s, int k) {
        if (k == 0) return 0;

        Map<Character, Integer> freq = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            freq.merge(rightChar, 1, Integer::sum);

            // Shrink window while constraint is violated
            while (freq.size() > k) {
                char leftChar = s.charAt(left);
                freq.merge(leftChar, -1, Integer::sum);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    /**
     * Converts 'exactly k distinct' to 'at most k' minus 'at most k-1'.
     * This is the standard trick for non-monotone constraints.
     */
    public static int exactlyKDistinct(String s, int k) {
        return longestSubstringKDistinct(s, k) - longestSubstringKDistinct(s, k - 1);
    }

    public static void main(String[] args) {
        System.out.println("At most 2 distinct in 'eceba': " + longestSubstringKDistinct("eceba", 2));       // 3
        System.out.println("At most 1 distinct in 'aa': " + longestSubstringKDistinct("aa", 1));             // 2
        System.out.println("At most 3 distinct in 'aabacbebebe': " + longestSubstringKDistinct("aabacbebebe", 3)); // 7
        System.out.println("Exactly 2 distinct in 'eceba': " + exactlyKDistinct("eceba", 2));                 // 3
        System.out.println("Exactly 3 distinct in 'eceba': " + exactlyKDistinct("eceba", 3));                 // 4
    }
}

package io.thecodeforge.algo;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class SlidingWindowMaximum {

    /**
     * Finds the maximum element in every window of size k.
     * Uses a monotonic deque — O(n) time, O(k) space.
     * Each element enters and exits the deque at most once.
     */
    public static int[] maxSlidingWindow(int[] arr, int k) {
        if (arr.length < k || k <= 0) return new int[0];

        int[] result = new int[arr.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // stores indices, values in decreasing order

        for (int i = 0; i < arr.length; i++) {
            // Remove indices outside the current window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove all elements smaller than arr[i] from the back
            // They can never be the max while arr[i] is in the window
            while (!deque.isEmpty() && arr[deque.peekLast()] < arr[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // Window is complete — record the max (front of deque)
            if (i >= k - 1) {
                result[i - k + 1] = arr[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        int[] result = maxSlidingWindow(arr, k);
        System.out.println("Array: " + Arrays.toString(arr));
        System.out.println("Max in each window of size " + k + ": " + Arrays.toString(result));
        // [3, 3, 5, 5, 6, 7]
    }
}