Sliding Window Technique for Longest Substring Problems

Welcome back! In our last lesson, we established the core "expand-and-shrink" logic for variable-size sliding windows. We saw how this dynamic approach allows us to efficiently find optimal subarrays without a fixed length k.

Today, we'll build directly on that foundation. Your goal for this lesson is to apply a variable-size window to solve longest-substring problems with a given constraint. You'll see how the general template we discussed remains constant, while the real art lies in defining the window's state and the specific condition that triggers the "shrink" phase. This skill of adapting a core pattern to different constraints is exactly what's needed to solve a wide range of interview problems efficiently.

Let's dive into some classic problems to see this pattern in action.

Example 1: Longest Substring with At Most K Distinct Characters

This is a canonical sliding window problem and a natural extension of the "Fruit Into Baskets" problem from our last lesson (which is just this problem with k=2).

The Problem: Given a string s and an integer k, find the length of the longest substring of s that contains at most k distinct characters.

For example, if s = "araaci" and k = 2, the longest substring with at most 2 distinct characters is "araa", so the answer is 4.

The expand-and-shrink logic is a perfect fit here. We need a way to track the distinct characters in our current window. A hash map is the ideal data structure for this, storing character frequencies.

• Expand: Move the right pointer, adding the new character to our hash map and updating its frequency.
• Invalid Condition: The number of distinct characters in our window exceeds k. In terms of our hash map, this means map.size() > k.
• Shrink: As long as the window is invalid, move the left pointer, decrease the frequency of the outgoing character, and if its frequency becomes zero, remove it from the map entirely.
• Update Result: After each potential shrink, the window is guaranteed to be valid. We calculate its length and update our maximum length found so far.

The following video provides an exceptionally clear, step-by-step walkthrough of this exact process.

As you saw, the core template is unchanged. The only new parts are the specific data structure (HashMap<Character, Integer>) and the condition (map.size() > k) that drives the while loop.

The animation below shows this dynamic process. While the example string is different, the principle of the window expanding and contracting to maintain a property (like a limited set of distinct characters) is the same.

Example 2: Longest Repeating Character Replacement

Let's look at a more subtle variation. Here, the constraint isn't a simple count of distinct characters but involves a "budget" for replacements. This is LeetCode problem 424.

The Problem: You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

For example, if s = "ABAB" and k = 2, the output is 4. We can replace the two 'A's with 'B's to get "BBBB".

How does our sliding window pattern adapt? The key is to formulate the validity condition. A window is "valid" if the number of characters we need to change to make it a solid block of one character is less than or equal to k.

This number is simply: window_length - count_of_most_frequent_character_in_window.

If this value is greater than k, the window is invalid, and we must shrink it.

• Window State: We need a hash map to track character frequencies and a variable to track the frequency of the most common character in the window so far.
• Expand: Move right, update the new character's frequency in the map, and update the max_frequency variable.
• Invalid Condition: (right - left + 1) - max_frequency > k.
• Shrink: If the window is invalid, move left and decrease the frequency of the outgoing character. Note: we don't need to re-calculate max_frequency during the shrink phase. The window is only growing, so we only care about the all-time max frequency we've seen for a valid window of the current best length. This is a subtle but important optimization.

Let's study a code implementation that demonstrates this logic.

Example 3: Maximum Erasure Value

This final example shows that the "longest substring" goal can sometimes be a proxy for another value. Here, we want the maximum sum of a valid subarray, not its length.

The Problem: You are given an array of positive integers nums. You want to erase a subarray containing unique elements. The score you get is the sum of its elements. Return the maximum score. (LeetCode 1695)

For nums = [4,2,4,5,6], the optimal subarray is [2,4,5,6] (sum 17).

The constraint is "unique elements," which we've seen before. The adaptation is in the result-tracking step.

• Window State: We need a way to track unique elements (a hash set is perfect) and a running sum of the elements in the window.
• Expand: Move right, add nums[right] to the current_sum.
• Invalid Condition: nums[right] is already in our hash set.
• Shrink: While the duplicate exists, remove nums[left] from the current_sum and the set, and increment left.
• Update Result: After each expansion (and ensuring validity), we update our result: max_score = max(max_score, current_sum).

This demonstrates the flexibility of the pattern—the core expand/shrink mechanism ensures we only consider valid subarrays, while the update step can be tailored to maximize length, sum, or any other metric.

A Framework for Problem-Solving

Your experience with LeetCode has likely given you an intuition for recognizing these patterns. Let's formalize that process. When you see a problem asking for the longest/shortest/max/min of a contiguous subarray/substring, you should immediately consider the sliding window.

Here's a thought process to follow:

1. Identify the Core Task: Is it about a contiguous sequence? Is there an optimization goal (longest, shortest, max sum)? This points towards a sliding window.

2. Determine Window Type: Is the size k given and fixed, or does it depend on a condition? For "longest substring" problems, it's almost always a variable-size window.

3. Define the Window State: What information do you need to track to check the condition?

   • Uniqueness? A set.
   • Frequencies or counts of distinct items? A hash map.
   • A running total? A sum variable.

4. Formulate the Invalidity Condition: This is the most critical step. Express the problem's constraint as a boolean condition for your while loop.

   • set.contains(newItem)
   • map.size() > k
   • window_length - max_freq > k
   • current_sum > target

5. Implement the Template: With the state and condition defined, plug them into the expand-and-shrink template you learned. Ensure your "update result" step matches the problem's goal (e.g., maximizing right - left + 1 or current_sum).

Conclusion

In this lesson, you've seen how to apply the versatile variable-size sliding window pattern to solve several "longest-substring" problems. You've practiced adapting the pattern by changing the data structures that maintain the window's state and, most importantly, by formulating the precise condition that makes a window invalid.

Key Takeaways:

• The expand-and-shrink template is a robust framework for a wide variety of "longest substring/subarray" problems.
• The primary skill is translating a problem's English-language constraint into a precise logical condition that can be checked against the window's state.
• The choice of data structure (set, map, etc.) to maintain the window's state is dictated by the requirements of this condition.
• The optimization goal (e.g., maximizing length vs. maximizing sum) determines what happens in the "update result" step of the algorithm.

In our next lesson, we will shift our focus slightly. We will continue using the variable-size window but apply it to "minimum-window" problems, such as finding the shortest substring that contains a required set of characters. This will introduce a small but important modification to our thinking about the expand-and-shrink phases.