Minimum Window Substring Explained | Sliding Window Technique in Python

Minimum Window Substring – Sliding Window Approach

While solving the Minimum Window Substring problem, I initially struggled to manage window validity correctly. The key challenge was ensuring that the current window contains all characters of the target string with correct frequency, while still keeping the window as small as possible.

Problem Intuition

The problem is a classic example of a variable-size sliding window. We expand the window to the right until it becomes valid, and once valid, we try to shrink it from the left to find the minimum-length substring.

To efficiently check window validity, instead of rechecking all characters every time, we maintain a frequency map and a counter that tracks how many characters are still required.

Approach

• Create a frequency map of the target string.
• Use two pointers (l and r) to represent the sliding window.
• Expand the window by moving r.
• Decrease the required count only when a needed character is found.
• Once all required characters are present, shrink the window from the left.
• Update the result whenever a smaller valid window is found.

Key Insight

The most important insight was understanding that:

• Extra characters should not affect window validity.
• The required counter should change only when a truly needed character enters or leaves the window.

Python Implementation

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "" or s == "":
            return ""

        freq_required = Counter(t)
        required = len(t)

        l = 0
        result = ""
        min_len = float("inf")

        for r in range(len(s)):
            if s[r] in freq_required:
                if freq_required[s[r]] > 0:
                    required -= 1
                freq_required[s[r]] -= 1

            while required == 0:
                if r - l + 1 < min_len:
                    min_len = r - l + 1
                    result = s[l:r+1]

                if s[l] in freq_required:
                    freq_required[s[l]] += 1
                    if freq_required[s[l]] > 0:
                        required += 1
                l += 1

        return result

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string s.
• Space Complexity: O(k), where k is the number of unique characters in t.

Final Thoughts

This problem helped reinforce an important sliding window principle: never revalidate the whole window if you can track validity incrementally. Once this idea clicks, many string and array window problems become much easier.