Sliding Window and Frequency Maps for Substring Problems

1. Warm-up: Longest Substring Without Repeating Characters

Let's start with a foundational problem: LeetCode 3, "Longest Substring Without Repeating Characters". This is a "find the longest" problem, so the template we learned in the previous lesson applies directly.

The condition is "without repeating characters." The most natural data structure to track this is a Set, which you can think of as a simplified frequency map where we only care if a character exists, not how many times.

To see how this works, let's watch a clear and concise explanation.

Let's break down the logic using the "find maximum length" template:

1. Initialize: left = 0, maxLength = 0, and our window state, charSet = new Set().
2. Expand Window: Iterate with a right pointer from the beginning to the end of the string.
3. Check Condition & Shrink: For the current character s[right], if it's already in our charSet, our window is invalid. We must shrink it from the left until the duplicate is removed.

   while (charSet.has(s[right])) {
     charSet.delete(s[left]);
     left++;
   }
   

4. Process Current Element: After ensuring the window is valid, add the current character.

   charSet.add(s[right]);
   

5. Update Result: The window is now valid and as large as it can be at this moment. We update our result.

   maxLength = Math.max(maxLength, right - left + 1);
   

This elegant solution processes each character at most twice, once by the right pointer and once by the left, giving us the optimal O(n) time complexity.

2. Fixed-Size Window: Permutations and Anagrams

Now, let's explore a variation where the window size is fixed. This pattern is perfect for problems where you need to find a permutation or anagram of a smaller string (pattern) within a larger string (str).

Consider "Find All Anagrams in a String" (LeetCode 438). An anagram is just a permutation. This means we are looking for any substring in str that is exactly the length of pattern and contains the exact same characters with the same frequencies.

The core idea is:

• Create a frequency map for the pattern.
• Slide a window of size pattern.length across str.
• For each window, check if its character frequencies match the pattern's frequencies.

A naive approach would be to rebuild the frequency map for the window at every single position, which is inefficient. The sliding window allows us to do this much faster. As the window slides one position to the right, we simply add the new character's frequency and remove the frequency of the character that just left the window.

The Optimized Approach with a Match Counter

Instead of comparing two full frequency maps at every slide, we can use a counter. Here's the logic for finding all anagrams:

1. Initialization:

   • Create patternFreq, a map of character frequencies in the pattern.
   • Initialize matched = 0. This will track how many characters from the pattern we have satisfied in our current window.
   • The number of unique characters in the pattern is our target, let's say required = Object.keys(patternFreq).length.

2. Slide and Update:

   • Iterate through the main string str with the right pointer.
   • Let endChar = str[right]. If endChar is in patternFreq, decrement its count in the map.
   • If the count for endChar becomes 0, it means we have the exact number of that character needed for an anagram, so we increment matched.

3. Check for Anagram:

   • Once matched === required, it means our current window might contain an anagram. We push the starting index (windowStart) to our results.

4. Shrink Window:

   • When the window size (right - left + 1) reaches the pattern.length, we must start shrinking it from the left to maintain the fixed size.
   • Let startChar = str[left]. If startChar was a required character (i.e., in patternFreq):
     • If its frequency was 0 before we put it back, it means we are about to lose a match, so we decrement matched.
     • Increment its frequency in the map (putting it back).
   • Finally, slide the window forward by incrementing left.

This technique is very efficient, as we are only performing simple arithmetic operations at each step, maintaining the O(N) time complexity where N is the length of the main string.

3. Deep Dive: Minimum Window Substring

Let's revisit the hard problem from our last lesson, "Minimum Window Substring" (LeetCode 76). This is the ultimate test of your understanding of variable-size windows and frequency maps. Mastering it is a huge step toward tackling FAANG-level medium/hard problems.

The problem asks for the smallest substring in s that contains all characters of t, including duplicates.

We use the "find minimum" template: expand until the condition is met, then shrink as much as possible while the condition holds. The complexity lies in efficiently tracking the condition: "does my window contain all characters of t?"

We'll use a new video resource for a fresh perspective and then a detailed article to truly cement the concepts.

To round out your understanding, we'll consult a detailed guide that covers not just the solution, but also how to think about it in an interview setting.

The core strategy for Minimum Window Substring is the two-map, two-counter approach:

• need Map: A frequency map of the target string t. This is static.
• window Map: A frequency map of the current sliding window. This is dynamic.
• required Counter: The number of unique characters in t.
• formed Counter: The number of unique characters in the current window that meet or exceed the required frequency in t.

You expand the window until formed === required. Once met, you are in the shrinking phase, where you find the smallest possible window by moving the left pointer until formed < required.

Conclusion

Today, we've solidified your command of the sliding window pattern by focusing on its most powerful partner: the frequency map. You've seen how this combination can tackle a range of substring problems, from finding the longest substring with unique characters to finding permutations and even the notoriously tricky minimum window substring.

Key Takeaways:

• Frequency maps are the engine of the sliding window for substring problems. They efficiently track the state of the characters within the window.
• The Set is a simple and effective frequency map for problems concerned only with character presence (e.g., "Longest Substring Without Repeating Characters").
• The fixed-size sliding window is a key sub-pattern for anagram and permutation problems. The "match counter" is a critical optimization to avoid comparing full maps.
• The two-map have/need (or formed/required) counter technique is the standard, efficient solution for complex variable-size window problems like "Minimum Window Substring".

Preview of the Next Lesson:
We will continue exploring sliding window variations. Our next lesson will introduce a specialized data structure, the deque (double-ended queue), to solve another class of problems: finding the maximum or minimum in a fixed-size sliding window (e.g., "Sliding Window Maximum" - LeetCode 239). This will add another powerful tool to your problem-solving arsenal.