Algorithms: Sliding Window

[1, 3, -1, -3, 5, 3, 6, 7]  window size = 3
 └──────┘
    └──────┘
       └──────┘

func fixedWindow(nums []int, k int) int {
    // Bước 1: build window đầu tiên
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }

    maxSum := windowSum

    // Bước 2: slide — thêm phải, bỏ trái
    for i := k; i < len(nums); i++ {
        windowSum += nums[i]       // thêm element mới vào phải
        windowSum -= nums[i-k]     // bỏ element cũ ở trái
        if windowSum > maxSum {
            maxSum = windowSum
        }
    }
    return maxSum
}

func variableWindow(s string) int {
    left := 0
    best := 0
    // state tracking tuỳ bài (map, counter, sum...)
    freq := make(map[byte]int)

    for right := 0; right < len(s); right++ {
        // 1. Expand: thêm s[right] vào window
        freq[s[right]]++

        // 2. Shrink: thu nhỏ khi vi phạm điều kiện
        for isInvalid(freq) {      // điều kiện tuỳ bài
            freq[s[left]]--
            if freq[s[left]] == 0 {
                delete(freq, s[left])
            }
            left++
        }

        // 3. Update answer
        windowLen := right - left + 1
        if windowLen > best {
            best = windowLen
        }
    }
    return best
}

"abcabcbb"
 a b c a b c b b
 └─────┘         window = "abc", len=3
   └─────┘       window = "bca", len=3
     └─────┘     window = "cab", len=3
       └───┘     window = "abc" → shrink khi thấy 'a' lại

func lengthOfLongestSubstring(s string) int {
    left := 0
    best := 0
    lastSeen := make(map[byte]int) // char → last index

    for right := 0; right < len(s); right++ {
        c := s[right]
        // Nếu char đã thấy VÀ nằm trong window hiện tại
        if idx, ok := lastSeen[c]; ok && idx >= left {
            left = idx + 1 // nhảy left qua vị trí sau lần thấy trước
        }
        lastSeen[c] = right
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

func minWindow(s, t string) string {
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    have, total := 0, len(need)
    left := 0
    minLen, minLeft := math.MaxInt32, 0
    window := make(map[byte]int)

    for right := 0; right < len(s); right++ {
        c := s[right]
        window[c]++
        // Check nếu char này đã đủ số lượng cần
        if need[c] > 0 && window[c] == need[c] {
            have++
        }

        // Shrink khi đã có đủ
        for have == total {
            if right-left+1 < minLen {
                minLen = right - left + 1
                minLeft = left
            }
            lc := s[left]
            window[lc]--
            if need[lc] > 0 && window[lc] < need[lc] {
                have--
            }
            left++
        }
    }

    if minLen == math.MaxInt32 {
        return ""
    }
    return s[minLeft : minLeft+minLen]
}

func maxSumSubarray(nums []int, k int) int {
    sum := 0
    for i := 0; i < k; i++ {
        sum += nums[i]
    }
    max := sum
    for i := k; i < len(nums); i++ {
        sum += nums[i] - nums[i-k]
        if sum > max {
            max = sum
        }
    }
    return max
}

func longestSubarrayKDistinct(s string, k int) int {
    freq := make(map[byte]int)
    left, best := 0, 0
    for right := 0; right < len(s); right++ {
        freq[s[right]]++
        for len(freq) > k {
            freq[s[left]]--
            if freq[s[left]] == 0 {
                delete(freq, s[left])
            }
            left++
        }
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

func maxSlidingWindow(nums []int, k int) []int {
    dq := []int{} // lưu index, giảm dần theo value
    result := []int{}

    for i := 0; i < len(nums); i++ {
        // Bỏ các index đã ra ngoài window
        for len(dq) > 0 && dq[0] < i-k+1 {
            dq = dq[1:]
        }
        // Bỏ các index nhỏ hơn nums[i] từ phía sau
        for len(dq) > 0 && nums[dq[len(dq)-1]] < nums[i] {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)

        if i >= k-1 {
            result = append(result, nums[dq[0]])
        }
    }
    return result
}