Minimum Window Substring Leetcode 76 [Python Solution]

Welcome to another Python coding session! Today, we are going to tackle a challenging problem from LeetCode – the Minimum Window Substring.

This problem falls under the category of Sliding Window, and it’s categorized as “Hard.” We’ll walk you through the problem, the constraints, a brute force approach, and then show you a much more efficient solution.

Problem Name: Minimum Window Substring

Difficulty: Hard

Category: Sliding Window

Companies: Airbnb

For reference, here’s the link to the problem on LeetCode.

Problem Overview

The problem statement is as follows:

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

If there is no such substring, return an empty string "".

The test cases will be generated such that the answer is unique.

Let’s illustrate this with some examples:

Example 1:

Input: s = "ADOBECODEBANC", `t = “ABC”

Output: "BANC"

Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:

Input: s = "a", t = "a"

Output: "a"

Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"

Output: ""

Explanation: Both ‘a’s from t must be included in the window.

Since the largest window of s only has one ‘a’, we return an empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

Now that we understand the problem, let’s dive into the solution.

Understanding Constraints

Before we get into the solution, it’s essential to understand the constraints of the problem.

The constraints tell us the limits within which our solution must operate efficiently.

• The lengths of strings s and t can be up to 105 characters.

This means our solution should be optimized for time and space to handle large inputs efficiently.

• The characters in both s and t can be either uppercase or lowercase English letters.

We need to ensure that our solution works for all possible characters.

Brute Force Approach

To solve this problem, let’s start with a brute force approach.

We’ll iterate through all possible substrings of s and check if each substring contains all the characters from t.

We’ll maintain a minimum window and update it whenever we find a smaller valid window.

Here’s the brute force approach in Python:

def minWindow(s: str, t: str) -> str:
    if t == "":
        return ""

    countT, window = {}, {}
    for c in t:
        countT[c] = 1 + countT.get(c, 0)

    have, need = 0, len(countT)
    res, resLen = [-1, -1], float("infinity")
    l = 0
    for r in range(len(s)):
        c = s[r]
        window[c] = 1 + window.get(c, 0)

        if c in countT and window[c] == countT[c]:
            have += 1

        while have == need:
            if (r - l + 1) < resLen:
                res = [l, r]
                resLen = r - l + 1
            window[s[l]] -= 1
            if s[l] in countT and window[s[l]] < countT[s[l]]:
                have -= 1
            l += 1
    l, r = res
    return s[l : r + 1] if resLen != float("infinity") else ""

This approach will work, but it’s not the most efficient solution.

It has a time complexity of O(m * n), where m is the length of string s and n is the length of string t.

We can do better.

Efficient Approach with Sliding Window

Let’s now discuss a more efficient approach using a sliding window.

The idea is to use two pointers, left and right, to maintain a sliding window that covers a potential minimum substring.

As we move the right pointer, we expand the window until we find a valid substring.

Once we have a valid substring, we try to minimize its length by moving the left pointer.

This process continues until we’ve considered all characters in s.

Here’s the Python code for this efficient approach:

def minWindow(s: str, t: str) -> str:
    if t == "":
        return ""

    countT, window = {}, {}
    for c in t:
        countT[c] = 1 + countT.get(c, 0)

    have, need = 0, len(countT)
    res, resLen = [-1, -1], float("infinity")
    l = 0
    for r in range(len(s)):
        c = s[r]
        window[c] = 1 + window.get(c, 0)

        if c in countT and window[c] == countT[c]:
            have += 1

        while have == need:
            if (r - l + 1) < resLen:
                res = [l, r]
                resLen = r - l + 1
            window[s[l]] -= 1
            if s[l] in countT and window[s[l]] < countT[s[l]]:
                have -= 1
            l += 1
    l, r = res
    return s[l : r + 1] if resLen != float("infinity") else ""

This efficient solution has a time complexity of O(m + n), which is much faster than the brute force approach.

It efficiently finds the minimum window substring that contains all characters from t.

Reasoning Behind Our Efficient Approach

Our efficient approach relies on a sliding window technique, which allows us to minimize the window length as we find valid substrings.

Here’s the reasoning behind our approach:

1. We start by initializing two dictionaries: countT to keep track of the characters in string t and their counts, and window to maintain the characters in the current window and their counts.
2. We use two pointers, left and right, to represent the window.

Initially, the window is empty, so both pointers are set to the start of the string.

3. As we move the right pointer to the right, we expand the window and update the window dictionary to reflect the characters in the current window.
4. When the count of a character in the window dictionary matches its count in the countT dictionary, it means we have a valid character in the window.

We increment the have counter.

5. We keep moving the right pointer to expand the window until we have all characters from t in the window (i.e., when have equals need).
6. Once we have a valid substring, we try to minimize its length by moving the left pointer to the right.

While moving the left pointer, we update the window dictionary and decrement the have counter.

We continue this process to find the minimum window.

7. We keep track of the minimum window length and the corresponding indices in the res list.

Once we’ve considered all characters in s, we return the substring from s with the minimum length.

This efficient approach ensures that we find the minimum window substring that contains all characters from t while minimizing time complexity.

Related Interview Questions By Company:

• Find Critical And Pseudo Critical Edges In Minimum Spanning Tree
• Reconstruct Itinerary LeetCode
• Reverse Nodes In K Group LeetCode

Related Interview Questions By Difficulty:

• Longest Repeating Character Replacement LeetCode
• Longest Substring Without Repeating Characters LeetCode
• Number Of Sub Arrays Of Size K And Avg Greater Than Or Equal To Threshold

Related Interview Questions By Category:

• Design Circular Queue LeetCode
• Minimum Window Substring LeetCode
• Wiggle Sort LeetCode

Conclusion

The Minimum Window Substring problem is a challenging one that can be efficiently solved using the sliding window technique.

We hope this Python solution and explanation have helped you understand how to tackle this problem.

In summary, the efficient approach uses two pointers to maintain a sliding window, efficiently finding the minimum window substring that contains all characters from t in O(m + n) time complexity.

This approach can handle large inputs and is optimized for both time and space.

We encourage you to implement this solution and explore more LeetCode problems to improve your problem-solving skills.

Happy coding!