Skip to main content

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.

Labels:

Comments

Post a Comment

Share your views on this blog😍😍

Popular posts from this blog

LeetCode 88 Explained: Four Approaches, Mistakes, Fixes & the Final Optimal Python Solution

Evolving My Solution to “Merge Sorted Array” A practical, beginner-friendly walkthrough showing four versions of my code (from a naive approach to the optimal in-place two-pointer solution). Includes explanations, complexity and ready-to-paste code. Problem Summary You are given two sorted arrays: nums1 with size m + n (first m are valid) nums2 with size n Goal: Merge nums2 into nums1 in sorted order in-place . Version 1 — Beginner Approach (Extra List) I merged into a new list then copied back. Works, but not in-place and uses extra memory. class Solution: def merge(self, nums1, m, nums2, n): result = [] p1 = 0 p2 = 0 for _ in range(m+n): if p1 >= m: result.extend(nums2[p2:n]) break elif p2 >= n: result.extend(nums1[p1:m]) break elif nu...
Post a Comment
Read more

Product of Array Except Self in Python | Prefix & Suffix Explained (LeetCode 238)

Problem Overview The Product of Array Except Self is a classic problem that tests your understanding of array traversal and optimization. The task is simple to state but tricky to implement efficiently. Given an integer array nums , you need to return an array such that each element at index i is equal to the product of all the elements in nums except nums[i] . The challenge is that: Division is not allowed The solution must run in O(n) time Initial Thoughts At first glance, it feels natural to compute the total product of the array and divide it by the current element. However, this approach fails because division is forbidden and handling zeroes becomes messy. This pushed me to think differently — instead of excluding the current element, why not multiply everything around it? That’s where the prefix and suffix product pattern comes in. Key Insight: Prefix & Suffix Products For every index i : Prefix product → product of all elements to t...
Post a Comment
Read more

Best Time to Buy and Sell Stock – LeetCode 121

Best Time to Buy and Sell Stock – LeetCode 121 (O(n) One-Pass Solution) The Best Time to Buy and Sell Stock problem from LeetCode 121 is a classic array and greedy problem frequently asked in coding interviews. The goal is to maximize profit by choosing a single day to buy and a later day to sell. Problem Statement You are given an array prices , where prices[i] represents the price of a stock on day i . You may complete at most one transaction (buy once and sell once). Input: prices = [7,1,5,3,6,4] Output: 5 Input: prices = [7,6,4,3,1] Output: 0 If no profit is possible, return 0 . Key Observations You must buy before you sell Only one transaction is allowed The selling day must come after the buying day Approach 1: Brute Force (Not Optimal) The brute force approach checks every possible pair of buying and selling days and calculates the profit. for i in range(n): for j in range(i+1, n): profit = max(profit, prices[j] - prices...
Post a Comment
Read more