Minimum Window Substring - LeetCode Solution

Problem Description

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that if there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

Link to the problem: https://leetcode.com/problems/minimum-window-substring/

Solution

To solve this problem, we can use the sliding window technique. We will define two pointers, left and right, which will point to the start and end of the window, respectively. We will move the right pointer until we have a window that contains all the characters in t. After that, we will move the left pointer to the right until we cannot move it any further without losing the window property. We will keep track of the minimum window we have seen so far and continue to move the pointers until we have gone through the entire string.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # Initialize two hash maps
        freq_t = {}
        freq_window = {}

        # Count the frequency of each character in t
        for char in t:
            freq_t[char] = freq_t.get(char, 0) + 1

        # Initialize the window and other variables
        left, right = 0, 0
        count = 0
        min_window = ""

        # Move the right pointer until we have a window that contains all the characters in t
        while right < len(s):
            # Increment the frequency of the character at the right pointer
            freq_window[s[right]] = freq_window.get(s[right], 0) + 1

            # If the frequency of the character at the right pointer is less than or equal to the frequency of that character in t, then we have found a valid character
            if s[right] in freq_t and freq_window[s[right]] <= freq_t[s[right]]:
                count += 1

            # Move the left pointer until we cannot move it any further without losing the window property
            while left <= right and count == len(t):
                # Update the minimum window
                if not min_window or len(s[left:right+1]) < len(min_window):
                    min_window = s[left:right+1]

                # Decrement the frequency of the character at the left pointer
                freq_window[s[left]] -= 1

                # If the frequency of the character at the left pointer becomes less than the frequency of that character in t, then we have lost a valid character
                if s[left] in freq_t and freq_window[s[left]] < freq_t[s[left]]:
                    count -= 1

                # Move the left pointer to the right
                left += 1

            # Move the right pointer to the right
            right += 1

        return min_window

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the string s. We only iterate through the string once, and each iteration involves moving the left and right pointers at most n times in total.

The space complexity of this solution is O(m), where m is the length of the string t. We use two hash maps to count the frequency of each character in t, which takes up O(m) space.

Conclusion

In this blog post, we saw how to solve the Minimum Window Substring problem using the sliding window technique. This problem can be tricky, but by breaking it down into smaller steps and using the sliding window technique, we were able to come up with an efficient solution. Happy Coding!😎

Minimum Window Substring - LeetCode Problem

Problem Description

Solution

Complexity Analysis

Conclusion