Sliding Window Maximum with Frequency Constraints

The sliding window maximum with frequency constraints is a classic algorithmic problem that requires maintaining window statistics while ensuring element frequencies meet specific criteria. This solution demonstrates efficient approaches using hash maps and deque-based techniques to handle both basic and advanced window constraints.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the maximum size of the input array or string we're working with?
2. Are duplicates allowed in the input, and if so, how should they be handled?
3. What is the expected return format - just the length of the window or the actual window itself?
4. Can we modify the input array/structure, or must we work with a copy?
5. What is the target time complexity for the follow-up - O(n) or better?

Restatement of the pattern: This pattern involves maintaining a sliding window over an array or string where we need to track and enforce constraints on element frequencies within that window. The window expands and contracts dynamically to meet specific frequency requirements, such as ensuring no element appears more than a certain number of times, or that all elements in the window satisfy some frequency-based condition.

Signal words and constraint shape: Key indicators include phrases like "maximum length of substring with at most k distinct characters," "find the longest subarray with no repeating elements," or "sliding window with frequency constraints." The constraint shape typically involves bounds on element counts, character frequencies, or occurrence limits within a moving window.

Assumptions:

• The input is a linear structure (array or string) that supports indexed access
• We're looking for a contiguous subsequence with specific frequency properties
• The constraint is typically on the count or frequency of elements, not their values

Scenario suitability: This pattern is best suited for static input scenarios where we can process the entire dataset once. It's less appropriate for streaming data where elements arrive continuously and we need to maintain real-time constraints, though it can be adapted for such cases with additional complexity.

The pattern works by leveraging the sliding window technique to efficiently explore all valid windows while maintaining frequency information through hash maps or similar structures, allowing us to find optimal solutions in linear time.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Find the longest/shortest substring/array with at most/at least K distinct elements"
• "Maximum window size where frequency of each element is bounded"
• "Sliding window" or "variable size sliding window"
• Problems involving "at most K" or "at least K" constraints on element frequencies

Why this pattern fits better than the most common alternatives: This pattern is specifically optimized for problems where we need to maintain frequency constraints within a sliding window. Unlike basic two-pointer approaches, it leverages the relationship between window size and element frequencies to achieve optimal O(n) time complexity. The key advantage over brute force is that we don't recompute frequencies from scratch for every window position.

Conditions where a variation or related pattern applies instead:

• If the constraint is on total sum rather than element counts, use prefix sums or two pointers with sum tracking
• If we need to find all valid windows rather than just the maximum size, consider storing intermediate states
• For problems with multiple independent constraints (e.g., max sum AND max distinct elements), we might need to combine approaches or use more complex state tracking

The core insight that makes this pattern work: The key insight is that for a valid window with at most K distinct elements, if we expand the right boundary and find a new element that would exceed K distinct elements, we must shrink the window from the left until we're back to at most K distinct elements. This allows us to maintain a valid window throughout the process, making it efficient to find optimal solutions.

This pattern is particularly effective when:

1. The constraint involves element frequencies or counts
2. We're looking for maximum or minimum window sizes under frequency bounds
3. The input can be processed in a single pass without needing to revisit previous elements

3. Approach Evolution

Interview communication script:

"My first instinct is to use a brute force approach where I check every possible substring and validate if it meets our frequency constraints. But that's O(n³) because for each starting position, I'd have to check all ending positions and count character frequencies, which is O(n²) for each substring. Let me think about how to optimize this.

I notice that we're looking for a contiguous subarray with specific frequency constraints, and we want the minimum length. This suggests a sliding window approach where I can maintain a valid window and shrink it when constraints are met.

If I maintain the constraint that all characters in my current window have frequencies within the allowed bounds, I can use two pointers to expand and contract the window. When I find a valid window, I can try to shrink it from the left while maintaining validity.

The key insight is that once I have a valid window, any smaller window that still satisfies constraints will be better. So I can expand the right pointer until I have a valid window, then contract from the left while maintaining validity to find the minimal valid window.

Let me think about invariants: I want to maintain that all characters in my current window have frequencies ≤ their maximum allowed frequency. When I expand the window, I might violate this constraint, so I need to contract from the left until it's satisfied again."

Brute-force approach and why it is not ideal:

The brute force approach would involve checking every possible substring to see if it satisfies the frequency constraints. For each starting position i, we'd check all ending positions j ≥ i, and for each such substring, count character frequencies to validate constraints. This results in O(n³) time complexity - O(n²) substrings and O(n) to validate each one. This is inefficient because we're recomputing character counts repeatedly and not leveraging the sliding nature of valid windows.

Improved approach and the key optimization:

The key optimization is to use a sliding window with two pointers. We maintain a window [left, right] that contains character frequencies within the allowed bounds. When we expand the window by moving right pointer, if we exceed frequency constraints, we contract from left until constraints are satisfied again. This way, each element is visited at most twice (once when expanding, once when contracting), giving us O(n) time complexity.

Final approach with step-by-step reasoning:

1. Use two pointers (left and right) to maintain a sliding window
2. Expand the window by moving right pointer, updating character frequencies
3. When any character exceeds its maximum frequency constraint, contract window from left until all constraints are satisfied
4. When window becomes valid (all frequencies within bounds), update minimum length if current window is smaller
5. Continue expanding and contracting until right pointer reaches end of string

Important invariants that must hold:

• All characters in current window have frequencies ≤ their maximum allowed frequency
• When a valid window is found, it's minimal for that position (we contract before recording)
• Window boundaries are always valid indices (0 to n-1)

4. Data Structure Choice

For the window with frequency constraints problem, I'll use a HashMap to track character frequencies within the sliding window.

Primary Data Structures

HashMap<Character, Integer> - This is the core data structure for tracking character frequencies in the current window. It allows O(1) average time complexity for insertions, deletions, and lookups, which is essential for maintaining the sliding window efficiently.

Why This Choice Works

The HashMap provides exactly what we need:

• Frequency tracking: Maps each character to its count in the current window
• Dynamic sizing: Automatically grows and shrinks as characters are added/removed
• Fast operations: O(1) average time for all required operations (increment, decrement, query)
• Memory efficient: Only stores characters that actually appear in the window

Space and Time Impact

Time Complexity:

• HashMap operations: O(1) average case
• Overall window management: O(n) where n is the string length

Space Complexity:

• O(k) where k is the number of unique characters in the string
• In worst case (all unique characters), this becomes O(n) where n is string length
• This is acceptable since we're only tracking characters present in the window

Helper Structures

Two pointers (integers) - While not a data structure per se, these serve as the sliding window bounds and are essential for maintaining the window state. They're simple integers that track the left and right boundaries of our active window.

The HashMap is the primary driver for solving this pattern, while the two pointers provide the sliding window mechanics that make frequency tracking meaningful. This combination enables us to efficiently expand and contract our window while maintaining accurate character counts.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: s = "abcabcbb", k = 2

Step 1: Initialize variables

• left = 0, maxLength = 0
• charCount map: {}

Step 2: Process character at index 0 ('a')

• Add 'a' to charCount: {a: 1}
• Window size = 1, max frequency = 1
• Since 1 ≤ 2, no shrinkage needed
• maxLength = max(0, 1) = 1

Step 3: Process character at index 1 ('b')

• Add 'b' to charCount: {a: 1, b: 1}
• Window size = 2, max frequency = 1
• Since 2 ≤ 2, no shrinkage needed
• maxLength = max(1, 2) = 2

Step 4: Process character at index 2 ('c')

• Add 'c' to charCount: {a: 1, b: 1, c: 1}
• Window size = 3, max frequency = 1
• Since 3 > 2, we must shrink window from left
• Remove 'a' from window: charCount = {b: 1, c: 1}
• Move left pointer to index 1
• maxLength = max(2, 2) = 2

Step 5: Process character at index 3 ('a')

• Add 'a' to charCount: {b: 1, c: 1, a: 1}
• Window size = 3, max frequency = 1
• Since 3 > 2, we must shrink window from left
• Remove 'b' from window: charCount = {c: 1, a: 1}
• Move left pointer to index 2
• maxLength = max(2, 2) = 2

Step 6: Process character at index 4 ('b')

• Add 'b' to charCount: {c: 1, a: 1, b: 1}
• Window size = 3, max frequency = 1
• Since 3 > 2, we must shrink window from left
• Remove 'c' from window: charCount = {a: 1, b: 1}
• Move left pointer to index 3
• maxLength = max(2, 2) = 2

Step 7: Process character at index 5 ('c')

• Add 'c' to charCount: {a: 1, b: 1, c: 1}
• Window size = 3, max frequency = 1
• Since 3 > 2, we must shrink window from left
• Remove 'a' from window: charCount = {b: 1, c: 1}
• Move left pointer to index 4
• maxLength = max(2, 2) = 2

Step 8: Process character at index 6 ('b')

• Add 'b' to charCount: {b: 2, c: 1}
• Window size = 3, max frequency = 2
• Since 3 > 2, we must shrink window from left
• Remove 'b' from window: charCount = {b: 1, c: 1}
• Move left pointer to index 5
• maxLength = max(2, 2) = 2

Step 9: Process character at index 7 ('b')

• Add 'b' to charCount: {b: 2, c: 1}
• Window size = 3, max frequency = 2
• Since 3 ≤ 2, no shrinkage needed
• maxLength = max(2, 3) = 3

Step 10: Process character at index 8 ('b')

• Add 'b' to charCount: {b: 3, c: 1}
• Window size = 4, max frequency = 3
• Since 4 > 2, we must shrink window from left
• Remove 'b' from window: charCount = {b: 2, c: 1}
• Move left pointer to index 6
• maxLength = max(3, 3) = 3

Step 11: Process character at index 9 ('b')

• Add 'b' to charCount: {b: 3, c: 1}
• Window size = 4, max frequency = 3
• Since 4 > 2, we must shrink window from left
• Remove 'b' from window: charCount = {b: 2, c: 1}
• Move left pointer to index 7
• maxLength = max(3, 3) = 3

Final result: The maximum length substring with at most 2 distinct characters is "bcb" with length 3.

The key insight in each step is that we maintain the invariant that the window contains at most k distinct characters, and we track the maximum valid window size seen so far. The algorithm correctly handles edge cases like when all characters are the same or when there are no valid substrings.

6. Java Solution

public class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        // HashMap to store frequency of elements in current window
        Map<Integer, Integer> freqMap = new HashMap<>();
        
        int left = 0;
        int maxLength = 0;
        
        // Sliding window approach
        for (int right = 0; right < nums.length; right++) {
            // Add current element to window
            int rightElement = nums[right];
            freqMap.put(rightElement, freqMap.getOrDefault(rightElement, 0) + 1);
            
            // Shrink window from left until frequency constraint is satisfied
            while (freqMap.get(rightElement) > k) {
                int leftElement = nums[left];
                freqMap.put(leftElement, freqMap.get(leftElement) - 1);
                
                if (freqMap.get(leftElement) == 0) {
                    freqMap.remove(leftElement);
                }
                
                left++;
            }
            
            // Update maximum length when window is valid
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

This solution uses a sliding window technique with a HashMap to track element frequencies. The key insight is that we expand the window by moving the right pointer and contract it from the left when any element exceeds frequency k. The algorithm maintains a valid window throughout execution and tracks the maximum valid window size encountered.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers (left and right) that traverse the array exactly once. Each element is visited at most twice - once by the right pointer and once by the left pointer when shrinking the window. The operations inside the loop (updating frequency map, checking constraints, updating result) are all O(1) operations.

Space Complexity: O(k) where k is the number of unique characters in the input string

The space complexity comes from the HashMap that stores character frequencies. In the worst case, if all characters in the string are unique, we might store up to n entries in the map. However, since we're looking for substrings with at most k distinct characters, the actual space usage is bounded by the number of unique characters in any valid substring, which is at most k.

The solution is optimal because:

1. We must examine each character at least once to determine if it contributes to a valid substring
2. The sliding window technique is the most efficient way to find the longest substring with bounded distinct characters
3. No better algorithm exists for this specific constraint - any approach that doesn't use the sliding window paradigm would require additional passes or more complex data structures

The O(n) time complexity is optimal for this problem since we cannot determine the longest valid substring without examining each character at least once, and our solution achieves this bound exactly.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with early return or zero-length window
• Single element: May require special handling for frequency constraints (e.g., frequency of 1)
• Zero target: May lead to empty result or special case handling

Duplicate Values and Repeated States

• Duplicate elements: The sliding window approach must properly account for frequency counts when duplicates exist
• Repeating patterns: When the same character/element appears multiple times, frequency tracking must maintain accurate counts
• Overcounting: Risk of counting elements multiple times when they appear in both left and right windows

Boundary Conditions

• Window size equals array length: When the entire array is the valid window, edge case handling is required
• Frequency threshold of 0: May require special logic for zero-frequency constraints
• Array with all same elements: Could lead to infinite expansion or incorrect window size calculation

Common Implementation Mistakes

• Incorrect frequency updates: Not properly decrementing the leftmost element's count when sliding the window
• Off-by-one errors: Mismanaging window bounds (left vs right pointers) leading to missing elements or including invalid ones
• Frequency threshold comparison: Using <= instead of < or vice versa when checking constraint satisfaction
• Not resetting frequency counts: When reusing the same frequency map across multiple test cases or function calls
• Integer overflow in large arrays: While unlikely with typical constraints, could be an issue with very large inputs

Frequency Tracking Specific Issues

• Negative frequency counts: Can occur if decrementing a count that's already zero, leading to incorrect window validation
• Missing elements in frequency map: Not initializing all required characters/elements in the frequency tracking structure
• Race conditions in multi-threaded scenarios: Though not applicable here, important to note when extending to concurrent environments

The solution must carefully maintain frequency counts and ensure that window bounds are properly managed throughout the sliding process to avoid these pitfalls.

9. Alternative Approaches

There are several alternative approaches to solving window problems with frequency constraints, each with different trade-offs:

1. Sliding Window with HashMap + Frequency Tracking Instead of using a TreeSet, we could maintain a HashMap to track character frequencies and manually manage the window. This approach requires more careful bookkeeping but avoids the overhead of TreeSet operations.

// Alternative: HashMap-based sliding window
Map<Character, Integer> freqMap = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
    char rightChar = s.charAt(right);
    freqMap.put(rightChar, freqMap.getOrDefault(rightChar, 0) + 1);
    
    while (freqMap.size() > k) {
        char leftChar = s.charAt(left++);
        freqMap.put(leftChar, freqMap.get(leftChar) - 1);
        if (freqMap.get(leftChar) == 0) {
            freqMap.remove(leftChar);
        }
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
}

2. Two-Pointer with Character Count Array If we know the character set is limited (e.g., only lowercase letters), we can use a fixed-size array instead of HashMap for O(1) access and updates. This is more efficient but less flexible.

3. Binary Search on Window Size We could binary search for the maximum valid window size by checking if a window of size m is achievable. This approach has O(n log n) time complexity but might be useful when we need to find the optimal window size rather than just any valid window.

Trade-offs:

• TreeSet provides automatic sorting but has O(log n) insertion/deletion
• HashMap requires manual frequency management but offers O(1) average operations
• Array-based approach is fastest for known character sets but less general
• Binary search is useful when we want to optimize window size rather than just existence

The TreeSet approach is chosen for its clean handling of the frequency constraint and automatic maintenance of window properties, making it more readable and less error-prone than manual frequency tracking.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic case with valid solution
        // Input: s = "abcabcbb", k = 2
        // Expected: 4 ("bcbc" or "cbca")
        System.out.println("Test 1: " + lengthOfLongestSubstringKDistinct("abcabcbb", 2));
        
        // Test Case 2: All characters are same
        // Input: s = "aaaa", k = 1
        // Expected: 4
        System.out.println("Test 2: " + lengthOfLongestSubstringKDistinct("aaaa", 1));
        
        // Test Case 3: k = 0
        // Input: s = "abc", k = 0
        // Expected: 0
        System.out.println("Test 3: " + lengthOfLongestSubstringKDistinct("abc", 0));
        
        // Test Case 4: k larger than string length
        // Input: s = "ab", k = 5
        // Expected: 2
        System.out.println("Test 4: " + lengthOfLongestSubstringKDistinct("ab", 5));
        
        // Test Case 5: Empty string
        // Input: s = "", k = 1
        // Expected: 0
        System.out.println("Test 5: " + lengthOfLongestSubstringKDistinct("", 1));
        
        // Test Case 6: Single character string
        // Input: s = "a", k = 1
        // Expected: 1
        System.out.println("Test 6: " + lengthOfLongestSubstringKDistinct("a", 1));
        
        // Test Case 7: Complex case with multiple valid substrings
        // Input: s = "aaabbbccc", k = 2
        // Expected: 6 ("bbbccc" or "aaabbb")
        System.out.println("Test 7: " + lengthOfLongestSubstringKDistinct("aaabbbccc", 2));
    }
}

Sample Test Cases:

1. Basic valid case: s = "abcabcbb", k = 2 → Expected: 4

   • Substring "bcbc" or "cbca" has exactly 2 distinct characters and length 4

2. All same characters: s = "aaaa", k = 1 → Expected: 4

   • Only one distinct character, so entire string is valid

3. k = 0: s = "abc", k = 0 → Expected: 0

   • No valid substring with 0 distinct characters

4. k > string length: s = "ab", k = 5 → Expected: 2

   • Maximum possible distinct characters is 2, so return entire string length

5. Empty string: s = "", k = 1 → Expected: 0

   • No characters to form any substring

6. Single character: s = "a", k = 1 → Expected: 1

   • One character with one distinct character

7. Complex case: s = "aaabbbccc", k = 2 → Expected: 6

   • Substring "bbbccc" or "aaabbb" has exactly 2 distinct characters and length 6

Tricky edge case: s = "aabbcc", k = 2 → Expected: 4

• Substrings like "aabb" or "bbcc" have exactly 2 distinct characters and length 4
• This tests that we properly handle repeated character patterns

11. Final Summary

The core idea is to use a sliding window approach with frequency counting to efficiently find the minimum window substring that contains all characters from a target string. This solution works by maintaining a dynamic window that expands to include new characters and contracts when all required characters are present, using hash maps to track character frequencies. The solution is optimal with O(n + m) time complexity where n is the length of the input string and m is the length of the target string, making it highly efficient for large inputs. The key insight is that we can avoid redundant character checks by maintaining a count of how many unique characters from the target string are still needed in the current window.