Sliding Window Maximum (Monotonic Deque)

🎯

Sliding Window Maximum (Monotonic Deque)

hardSLIDING_WINDOWAmazonGoogleMicrosoft

Imagine monitoring the highest temperature in every hour-long window throughout a day to detect heat spikes efficiently.

💡 This problem asks for the maximum value in every contiguous subarray of fixed size. Beginners often struggle because a naive approach is too slow, and the optimal solution requires a clever data structure (monotonic deque) that maintains candidates efficiently.

📋

Problem Statement

Given an integer array nums and an integer k, there is a sliding window of size k which moves from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the maximum of the k numbers in the window.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^41 ≤ k ≤ nums.length

💡

Example

Input"nums = [1,3,-1,-3,5,3,6,7], k = 3"

Output[3,3,5,5,6,7]

The sliding windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]. Their maximums are 3, 3, 5, 5, 6, 7 respectively.

• k = 1 → output is the array itself
• All elements equal → output is repeated element
• Strictly increasing array → max is last element in each window
• Strictly decreasing array → max is first element in each window

⚠️

Common Mistakes

Not removing indices outside the window from the front of the deque

Incorrect maximum values as outdated elements remain

✅ Always check and remove front index if it is out of the current window

Removing elements from the front instead of the back when maintaining decreasing order

Deque order breaks, resulting in wrong max values

✅ Remove smaller elements from the back, not the front

Starting to append results before the first full window is formed

Output array is shorter or contains invalid values

✅ Only append max after i >= k - 1

Using values instead of indices in the deque

Cannot check if elements are out of window efficiently

✅ Store indices in deque to track window boundaries

Using a naive heap without removing outdated elements

Heap top may be invalid, causing wrong max values

✅ Remove elements from heap whose indices are out of window

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem's core: finding maximums in windows. Though inefficient, it builds intuition about the sliding window concept.

Intuition

For each window of size k, scan all elements inside it to find the maximum.

Algorithm

1. Iterate over the array from index 0 to n-k.
2. For each position, scan the next k elements to find the maximum.
3. Store the maximum in the result array.
4. Return the result array after processing all windows.

💡 This approach is straightforward but inefficient because it repeats scanning overlapping elements multiple times.

</>

Code

from typing import List

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    result = []
    for i in range(n - k + 1):
        window_max = nums[i]
        for j in range(i + 1, i + k):
            if nums[j] > window_max:
                window_max = nums[j]
        result.append(window_max)
    return result

# Example usage
if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

for i in range(n - k + 1):Iterate over all valid window start indices to cover every window

window_max = nums[i]Initialize max for current window with first element to start comparison

for j in range(i + 1, i + k):Scan remaining elements in the current window to find max

if nums[j] > window_max:Update max if a larger element is found to keep track of max

result.append(window_max)Store the max for this window in the result to build final output

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int windowMax = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] > windowMax) {
                    windowMax = nums[j];
                }
            }
            result[i] = windowMax;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res));
    }
}

Line Notes

for (int i = 0; i <= n - k; i++) {Loop over all window start indices to cover every possible window

int windowMax = nums[i];Initialize max for current window to first element for comparison

for (int j = i + 1; j < i + k; j++) {Check all elements in the window to find max

if (nums[j] > windowMax) {Update max if current element is larger to track max

result[i] = windowMax;Save max for this window in the result array

#include <iostream>
#include <vector>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    for (int i = 0; i <= n - k; i++) {
        int windowMax = nums[i];
        for (int j = i + 1; j < i + k; j++) {
            if (nums[j] > windowMax) {
                windowMax = nums[j];
            }
        }
        result.push_back(windowMax);
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int val : res) cout << val << " ";
    cout << endl;
    return 0;
}

Line Notes

for (int i = 0; i <= n - k; i++) {Iterate over all valid window start positions to cover all windows

int windowMax = nums[i];Initialize max for current window with first element

for (int j = i + 1; j < i + k; j++) {Scan all elements in the window to find max

if (nums[j] > windowMax) {Update max if a larger element is found

result.push_back(windowMax);Append max to result vector to build output

function maxSlidingWindow(nums, k) {
    const n = nums.length;
    const result = [];
    for (let i = 0; i <= n - k; i++) {
        let windowMax = nums[i];
        for (let j = i + 1; j < i + k; j++) {
            if (nums[j] > windowMax) {
                windowMax = nums[j];
            }
        }
        result.push(windowMax);
    }
    return result;
}

// Example usage
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

for (let i = 0; i <= n - k; i++) {Loop over all starting indices of windows to cover every window

let windowMax = nums[i];Initialize max for current window to first element

for (let j = i + 1; j < i + k; j++) {Check all elements inside the window to find max

if (nums[j] > windowMax) {Update max if current element is bigger to track max

result.push(windowMax);Add max of current window to results array

⏱

Complexity

TimeO(n*k)

SpaceO(n-k+1)

For each of the n-k+1 windows, we scan k elements to find the max, resulting in O(n*k) time. The output array takes O(n-k+1) space.

💡 For n=100,000 and k=10,000, this means 1 billion operations, which is too slow for large inputs.

Interview Verdict: TLE (Time Limit Exceeded) on large inputs

This approach is too slow for large inputs but is useful to understand the problem and verify correctness on small inputs.

🧠

Using Max-Heap (Priority Queue)

💡 This approach improves over brute force by using a max-heap to track the maximum in the current window, but still has overhead due to heap operations.

Intuition

Maintain a max-heap of elements in the current window. Remove elements that fall out of the window and peek the max at each step.

Algorithm

1. Initialize a max-heap and a result list.
2. Add first k elements to the heap.
3. For each window starting from index k, remove elements outside the window from the heap.
4. Add the current max (heap top) to the result.
5. Slide the window by adding the new element and removing the old one.
6. Return the result list.

💡 This approach uses a data structure to avoid scanning the entire window each time but requires careful removal of outdated elements.

</>

Code

from typing import List
import heapq

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    result = []
    # Python heapq is min-heap, so store negative values for max-heap
    heap = []
    for i in range(k):
        heapq.heappush(heap, (-nums[i], i))
    result.append(-heap[0][0])

    for i in range(k, n):
        heapq.heappush(heap, (-nums[i], i))
        # Remove elements outside the window
        while heap[0][1] <= i - k:
            heapq.heappop(heap)
        result.append(-heap[0][0])
    return result

# Example usage
if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

heap = []Initialize empty heap to store elements with indices for efficient max retrieval

heapq.heappush(heap, (-nums[i], i))Push negative value to simulate max-heap and store index for window tracking

while heap[0][1] <= i - k:Remove elements outside the current window to keep heap valid

result.append(-heap[0][0])Append current max (negated back) to result to build output

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);
        for (int i = 0; i < k; i++) {
            maxHeap.offer(new int[]{nums[i], i});
        }
        result[0] = maxHeap.peek()[0];
        for (int i = k; i < n; i++) {
            maxHeap.offer(new int[]{nums[i], i});
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            result[i - k + 1] = maxHeap.peek()[0];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res));
    }
}

Line Notes

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);Create max-heap based on element values for efficient max retrieval

maxHeap.offer(new int[]{nums[i], i});Add element and its index to heap to track window elements

while (maxHeap.peek()[1] <= i - k) {Remove elements outside the current window to maintain correctness

result[i - k + 1] = maxHeap.peek()[0];Record current max from heap top to build output

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    priority_queue<pair<int,int>> maxHeap; // stores (value, index)
    for (int i = 0; i < k; i++) {
        maxHeap.push({nums[i], i});
    }
    result.push_back(maxHeap.top().first);
    for (int i = k; i < n; i++) {
        maxHeap.push({nums[i], i});
        while (maxHeap.top().second <= i - k) {
            maxHeap.pop();
        }
        result.push_back(maxHeap.top().first);
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int val : res) cout << val << " ";
    cout << endl;
    return 0;
}

Line Notes

priority_queue<pair<int,int>> maxHeap;Max-heap storing (value, index) pairs for efficient max retrieval

maxHeap.push({nums[i], i});Add current element with index to heap to track window elements

while (maxHeap.top().second <= i - k) {Remove elements outside the sliding window to maintain correctness

result.push_back(maxHeap.top().first);Add current max to result to build output

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }
    bubbleUp(i) {
        while (i > 0 && this.heap[this.parent(i)][0] < this.heap[i][0]) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return top;
    }
    bubbleDown(i) {
        let largest = i;
        const left = this.left(i);
        const right = this.right(i);
        if (left < this.heap.length && this.heap[left][0] > this.heap[largest][0]) largest = left;
        if (right < this.heap.length && this.heap[right][0] > this.heap[largest][0]) largest = right;
        if (largest !== i) {
            this.swap(i, largest);
            this.bubbleDown(largest);
        }
    }
    top() {
        return this.heap[0];
    }
}

function maxSlidingWindow(nums, k) {
    const n = nums.length;
    const maxHeap = new MaxHeap();
    const result = [];
    for (let i = 0; i < k; i++) {
        maxHeap.push([nums[i], i]);
    }
    result.push(maxHeap.top()[0]);
    for (let i = k; i < n; i++) {
        maxHeap.push([nums[i], i]);
        while (maxHeap.top()[1] <= i - k) {
            maxHeap.pop();
        }
        result.push(maxHeap.top()[0]);
    }
    return result;
}

// Example usage
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

class MaxHeap {Custom max-heap implementation to support element removal and max retrieval

maxHeap.push([nums[i], i]);Add element and index to heap to track window elements

while (maxHeap.top()[1] <= i - k) {Remove elements outside the current window to maintain correctness

result.push(maxHeap.top()[0]);Add current max to result array to build output

⏱

Complexity

TimeO(n log k)

SpaceO(k) amortized

Each insertion and removal from the heap costs O(log k), done n times, resulting in O(n log k) time. Space is O(k) amortized for the heap, as outdated elements are lazily removed.

💡 For n=100,000 and k=1000, this means about 1.5 million operations, which is better but still not optimal.

Interview Verdict: Accepted but slower than optimal

This approach is a good improvement but still not the best; it shows the value of data structures but can be optimized further.

🧠

Optimal: Monotonic Deque

💡 This approach uses a double-ended queue to maintain indices of elements in decreasing order, allowing O(n) time complexity by efficiently discarding irrelevant elements.

Intuition

Keep indices of elements in a deque such that the values are in decreasing order. The front always holds the max for the current window. Remove indices that fall out of the window or whose values are smaller than the current element.

Algorithm

1. Initialize an empty deque to store indices.
2. Iterate over each element index i in nums.
3. Remove indices from the back whose corresponding values are less than nums[i].
4. Add current index i to the back of the deque.
5. Remove the front index if it is out of the current window (i - k).
6. If the window has reached size k, append the value at the front of the deque to the result.
7. Return the result array.

💡 This algorithm cleverly maintains a data structure that always knows the max in O(1) time, avoiding repeated scanning or costly heap operations.

</>

Code

from typing import List
from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    dq = deque()  # stores indices
    result = []
    for i in range(n):
        # Remove smaller elements from the back
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        # Remove front if out of window
        if dq[0] == i - k:
            dq.popleft()
        # Append max to result when window is full
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Example usage
if __name__ == '__main__':
    print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

dq = deque()Initialize deque to store indices of candidates for max to maintain order

while dq and nums[dq[-1]] < nums[i]:Remove indices whose values are smaller than current element to keep deque decreasing

if dq[0] == i - k:Remove front index if it is outside the current window to maintain valid window

if i >= k - 1:Start adding max values to result once window is full to build output

import java.util.*;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            if (dq.peekFirst() == i - k) {
                dq.pollFirst();
            }
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(res));
    }
}

Line Notes

Deque<Integer> dq = new LinkedList<>();Deque stores indices of elements in decreasing order to track max candidates

while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {Remove smaller elements from the back to maintain decreasing order

if (dq.peekFirst() == i - k) {Remove front if it is out of the window to keep window valid

if (i >= k - 1) {Add current max to result once window is full to build output

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    deque<int> dq; // stores indices
    vector<int> result;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.front() == i - k) {
            dq.pop_front();
        }
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (int val : res) cout << val << " ";
    cout << endl;
    return 0;
}

Line Notes

deque<int> dq;Deque to store indices of potential max elements to maintain order

while (!dq.empty() && nums[dq.back()] < nums[i]) {Remove smaller elements from the back to keep deque decreasing

if (dq.front() == i - k) {Remove front if it is outside the window to maintain valid window

if (i >= k - 1) {Add max element to result once window is full to build output

function maxSlidingWindow(nums, k) {
    const n = nums.length;
    const dq = [];
    const result = [];
    for (let i = 0; i < n; i++) {
        while (dq.length && nums[dq[dq.length - 1]] < nums[i]) {
            dq.pop();
        }
        dq.push(i);
        if (dq[0] === i - k) {
            dq.shift();
        }
        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }
    return result;
}

// Example usage
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

const dq = [];Deque implemented as array storing indices to maintain order

while (dq.length && nums[dq[dq.length - 1]] < nums[i]) {Remove smaller elements from the back to keep deque decreasing

if (dq[0] === i - k) {Remove front if it is outside the window to maintain valid window

if (i >= k - 1) {Add max element to result once window is full to build output

⏱

Complexity

TimeO(n)

SpaceO(k)

Each element is pushed and popped at most once from the deque, resulting in linear time. Space is O(k) for the deque and output.

💡 For n=100,000, this means about 200,000 operations, which is efficient for large inputs.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its optimal time and space complexity.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the monotonic deque approach for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*k)	O(n-k+1)	No	N/A	Mention only - never code
2. Max-Heap	O(n log k)	O(k)	No	N/A	Good to mention as improvement, but not optimal
3. Monotonic Deque	O(n)	O(k)	No	N/A	Code this approach for best results

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding.Discuss the max-heap approach as an improvement.Present the monotonic deque as the optimal solution.Code the monotonic deque solution carefully.Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code: 10min → Test & optimize: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to optimal, knowledge of data structures (deque), and coding accuracy.

Common Follow-ups

• What if k = 1? → Return the array itself.
• Can you solve it if the window size varies? → Use a balanced tree or segment tree.
• How to find minimum instead of maximum? → Modify comparison in deque.
• What if the array is circular? → Handle wrap-around indices carefully.

💡 These follow-ups test your adaptability and deeper understanding of the sliding window and data structure concepts.

🔍

Pattern Recognition

When to Use

1) Need max/min in every fixed-size subarray; 2) Sliding window moves one step at a time; 3) Overlapping windows with repeated elements; 4) Efficient O(n) solution needed.

Signature Phrases

sliding window of size kmaximum of the k numberswindow moves right by one position

NOT This Pattern When

Problems asking for maximum subarray sum or variable window sizes without fixed k are different patterns.

Similar Problems

239. Sliding Window Maximum - classic problem using monotonic deque862. Shortest Subarray with Sum at Least K - uses monotonic queue for sums

Practice

1. You are given two strings s and p. You need to find all start indices in s where a substring is an anagram of p. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings of length equal to p and comparing frequency maps.

B. Sliding window with frequency map comparison and count matching optimization.

C. Dynamic programming to build a table of substring matches based on character counts.

D. Greedy approach by sorting each substring and comparing with sorted p.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding all anagrams of p in s efficiently, ideally in linear time.

2. Step 2: Evaluate algorithmic approaches

   Brute force (checking all substrings) is O(n*m), sorting each substring is O(n*m log m), and DP is not naturally suited here. Sliding window with frequency map and count matching optimizes to O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with count matching is known optimal for fixed-size anagram search [OK]

Hint: Sliding window with count matching -> O(n) time [OK]

Common Mistakes:

• Thinking sorting each substring is efficient enough
• Assuming DP applies directly
• Using brute force for large inputs

2. Consider the following Python function implementing the sliding window approach to find the maximum sum subarray of size k. What is the value of window_sum after the second iteration of the for-loop when called with arr = [1, 3, 2, 6] and k = 2?

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

easy

A. 8

B. 9

C. 5

D. 7

Solution

1. Step 1: Initialize variables

   window_sum = sum(arr[:2]) = 1 + 3 = 4, max_sum = 4

2. Step 2: Iterate and update window_sum

   First iteration (i=2): window_sum = 4 + arr[2] - arr[0] = 4 + 2 - 1 = 5 Second iteration (i=3): window_sum = 5 + arr[3] - arr[1] = 5 + 6 - 3 = 8

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   window_sum after second iteration is 8 [OK]

Hint: Track window_sum updates carefully per iteration [OK]

Common Mistakes:

• Off-by-one errors in loop index
• Confusing window_sum with max_sum
• Forgetting to subtract the element leaving the window

3. What is the time complexity of the optimal sliding window solution for counting the number of subarrays with exactly k odd numbers in an array of length n?

medium

A. O(k * n) because the window size depends on k

B. O(n^2) due to nested loops inside the sliding window

C. O(n log n) due to sorting or binary search steps

D. O(n) because each element is visited at most twice by left and right pointers

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves from 0 to n-1 once; left pointer only moves forward when odd_count > k.

2. Step 2: Count total operations

   Each pointer moves at most n times, so total operations are O(n) + O(n) = O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window two-pointer approach is linear time [OK]

Hint: Two pointers each move at most n times [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing k factor as multiplier
• Thinking sorting is involved

4. Suppose the fruits problem is modified so that you can pick fruits from trees non-contiguously but still want to maximize the total number of fruits collected with at most two fruit types. Which approach correctly solves this variant?

hard

A. Count total occurrences of each fruit type and sum the two largest counts

B. Sort fruits and use two pointers to find longest contiguous segment with two types

C. Use dynamic programming to find longest subsequence with at most two distinct fruits

D. Use the same sliding window approach since it handles at most two fruit types

Solution

1. Step 1: Understand non-contiguous picking

   Since picking is non-contiguous, order does not matter; we want max total fruits of two types.

2. Step 2: Optimal solution is sum of two largest fruit counts

   Count frequency of each fruit type, pick top two counts, sum them for max fruits.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Non-contiguous means subsequence, so frequency sums suffice [OK]

Hint: Non-contiguous -> sum top two fruit counts [OK]

Common Mistakes:

• Applying sliding window to non-contiguous
• Using DP unnecessarily
• Sorting loses subsequence property

5. Suppose the problem is modified so that characters can be replaced multiple times but replacements have different costs, and you want the longest substring with total replacement cost ≤ k. Which of the following approaches correctly adapts the sliding window solution to handle variable replacement costs?

hard

A. Use the same sliding window with frequency array but replace max_count with the character having minimum replacement cost in the window.

B. Maintain a sliding window and track the total replacement cost dynamically; shrink window when total cost exceeds k, updating frequencies accordingly.

C. Use brute force to check all substrings and sum replacement costs for each, since sliding window cannot handle variable costs.

D. Apply a fixed-size sliding window equal to k and count max frequency character inside it.

Solution

1. Step 1: Understand variable replacement costs

   Replacement cost varies per character, so max frequency alone is insufficient to determine validity of window.

2. Step 2: Adapt sliding window to track total replacement cost

   Maintain a running sum of replacement costs for characters that differ from the chosen target character in the window. Shrink window when total cost > k.

3. Step 3: Reject naive or fixed-size windows

   Fixed-size windows or brute force are inefficient or incorrect for variable costs.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Dynamic cost tracking with window shrinkage handles variable costs [OK]

Hint: Track total replacement cost dynamically, not just counts [OK]

Common Mistakes:

• Assuming max frequency logic applies unchanged
• Using fixed window size despite variable costs
• Reverting to brute force unnecessarily