Sliding Window

The sliding window technique maintains a contiguous sub-segment [left..=right] over an array or string, incrementally updating window state as right advances by 1 step and left advances to restore the window constraint. Because both left and right only move forward from 0 to n, a sliding window processes all valid sub-segments in $O(n)$ linear time (at most $2n$ pointer increments total) instead of $O(n^2)$ nested loops.

Variable-Size Sliding Window (`left` and `right` both move monotonically `0 -> n`):

  [ a | b | c | b | d | e | a ]
        ^-----------^
      `left`      `right`
  1. Expand `right`: Add `arr[right]` into window state
  2. While window violates constraint: Remove `arr[left]` & increment `left += 1`
  3. Record optimal valid window length `right - left + 1`!

Fixed-Size vs Variable-Size Sliding Windows

1. Fixed-Size Sliding Window Sum

/// Finds the maximum sum of any contiguous subarray of exact length `k` in O(n) time.
pub fn max_fixed_window_sum(nums: &[i64], k: usize) -> Option<i64> {
    if k == 0 || k > nums.len() {
        return None;
    }

    let mut window_sum: i64 = nums[..k].iter().sum();
    let mut best_sum = window_sum;

    for i in k..nums.len() {
        window_sum += nums[i] - nums[i - k];
        best_sum = best_sum.max(window_sum);
    }

    Some(best_sum)
}

2. Variable-Size Sliding Window: Longest Substring Without Repeating Bytes

Using a 256-entry stack lookup table (last_seen: [Option<usize>; 256]) or frequency array allows advancing left in $O(1)$ time with zero heap allocations:

/// Computes the length of the longest contiguous substring of `s` with all unique ASCII bytes
/// in O(n) time and O(1) stack space.
pub fn longest_unique_substring_len(s: &str) -> usize {
    let bytes = s.as_bytes();
    let mut freq = [0u32; 256];
    let mut left = 0usize;
    let mut max_len = 0usize;

    for (right, &b) in bytes.iter().enumerate() {
        freq[b as usize] += 1;

        // While the newly added byte `b` has a duplicate in `[left..=right]`, advance `left`:
        while freq[b as usize] > 1 {
            freq[bytes[left] as usize] -= 1;
            left += 1;
        }

        max_len = max_len.max(right - left + 1);
    }

    max_len
}

/// Finds the minimum length of a contiguous subarray of positive integers whose sum >= `target`.
pub fn min_subarray_len_at_least(nums: &[u64], target: u64) -> Option<usize> {
    let mut left = 0usize;
    let mut sum = 0u64;
    let mut best: Option<usize> = None;

    for (right, &val) in nums.iter().enumerate() {
        sum += val;
        while sum >= target {
            let len = right - left + 1;
            best = Some(best.map_or(len, |b| b.min(len)));
            sum -= nums[left];
            left += 1;
        }
    }

    best
}

fn main() {
    assert_eq!(max_fixed_window_sum(&[2, 1, 5, 1, 3, 2], 3), Some(9)); // [5, 1, 3]
    assert_eq!(longest_unique_substring_len("abcabcbb"), 3);            // "abc"
    assert_eq!(min_subarray_len_at_least(&[2, 3, 1, 2, 4, 3], 7), Some(2)); // [4, 3]

    println!(
        "Max k=3 window sum: {:?}, longest unique substring: {}, min subarray >= 7: {:?}",
        max_fixed_window_sum(&[2, 1, 5, 1, 3, 2], 3),
        longest_unique_substring_len("abcabcbb"),
        min_subarray_len_at_least(&[2, 3, 1, 2, 4, 3], 7)
    );
}

Max k=3 window sum: Some(9), longest unique substring: 3, min subarray >= 7: Some(2)