/**
 * Maximum sum of any subarray of size k
 *
 * Window slides: [1,2,3] sum=6 → [2,3,4] sum=9 → [3,4,5] sum=12
 *                           │
 *                     remove1 add4 → 6 - 1 + 4 = 9 ✓
 */
function maxSumSubarray(arr, k) {
    let windowSum = 0;
    let maxSum = 0;

    // Build initial window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide window
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];  // Add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)
// Time: O(n), Space: O(1)

/**
 * Smallest subarray with sum >= target
 *
 * Expand right until sum >= target, then shrink from left while maintaining condition.
 */
function minSubarrayLen(arr, target) {
    let minLen = Infinity;
    let windowSum = 0;
    let left = 0;

    for (let right = 0; right < arr.length; right++) {
        windowSum += arr[right];  // Expand window

        // Shrink window from left while condition holds
        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            windowSum -= arr[left];  // Remove leftmost element
            left++;                   // Move left forward
        }
    }

    return minLen === Infinity ? 0 : minLen;
}

console.log(minSubarrayLen([2, 3, 1, 2, 4, 3], 7)); // 2 ([4,3])
// Time: O(n), Space: O(1)

/**
 * Longest substring without repeating characters
 *
 * Use a Map to track character positions.
 * When a repeat is found, jump left to after the previous occurrence.
 */
function lengthOfLongestSubstring(s) {
    const charMap = new Map();  // character → index
    let maxLen = 0;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];

        // If char already in window, move left past it
        if (charMap.has(char) && charMap.get(char) >= left) {
            left = charMap.get(char) + 1;
        }

        charMap.set(char, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
// Time: O(n), Space: O(min(n, 26)) — 26 for alphabet

// ❌ WRONG — Not checking if window condition holds
while (windowSum >= target) {
    minLen = Math.min(...);
    windowSum -= arr[left];
    left++;
}

// ✅ CORRECT — Always check condition before updating
while (windowSum >= target) {
    minLen = Math.min(minLen, right - left + 1);
    windowSum -= arr[left];
    left++;
}