Minimum Window Substring 🎯

Welcome to a comprehensive guide on the Minimum Window Substring problem! This lesson is designed to help you understand and solve one of the most popular algorithmic problems, especially in interviews. Let's dive in!

What is Minimum Window Substring? 📝

In the Minimum Window Substring problem, we are given two strings S1 and S2, and the goal is to find the shortest possible substring in S1 that contains all the characters of S2 at least once. This substring should be present in S1 without any duplicates.

Why is this problem important? 💡

The Minimum Window Substring problem is essential in many real-world applications, such as text analysis, bioinformatics, and data compression. It helps us understand and handle string manipulation effectively.

Breaking it Down 📝

Let's break the problem into smaller, manageable steps:

Step 1: Create Frequency Maps

First, we need to create frequency maps for both S1 and S2. A frequency map, also known as a hash map or dictionary, is a data structure that stores the count of each character in a string.

python

def create_frequency_map(s):
    freq = {}
    for char in s:
        if char in freq:
            freq[char] += 1
        else:
            freq[char] = 1
    return freq

Step 2: Find the Minimum Required Frequency

Next, we find the minimum required frequency for each character in S2 by taking the minimum value from the frequency map of S2.

python

def min_required_frequency(freq_s2):
    min_freq = float('inf')
    for char, count in freq_s2.items():
        min_freq = min(min_freq, count)
    return min_freq

Step 3: Sliding Window Approach

Now, we apply the sliding window approach to find the minimum window substring. We start with an empty window and move it along S1, updating the frequency map of the window and the remaining string (S1 without the window). If the frequency map of the window and the remaining string match the frequency map of S2 with the minimum required frequency, we've found the minimum window substring.

python

def min_window_substring(s1, s2):
    freq_s2 = create_frequency_map(s2)
    min_freq = min_required_frequency(freq_s2)
    window_start = 0
    min_window = ''
    current_freq = create_frequency_map('')

    for window_end in range(len(s1)):
        current_freq[s1[window_end]] += 1
        while current_freq[s1[window_end]] > min_freq:
            current_freq[s1[window_start]] -= 1
            if current_freq[s1[window_start]] < min_freq:
                current_freq.pop(s1[window_start])
            window_start += 1

        if len(current_freq) == len(freq_s2):
            min_window = s1[window_start:window_end+1]
            break

    return min_window

Putting it all Together 💡

Let's test our function with some examples:

python

s1 = "ADOBECODEBANC"
s2 = "ABC"
print(min_window_substring(s1, s2))  # Output: "BAN"

Quiz 🎯

That's it for today! In the next lesson, we'll dive deeper into the sliding window approach and tackle more challenging problems together. Happy coding! 🚀