Minimum Window Substring

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

from collections import Counter

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

        t_counts = Counter(t)
        window_counts = Counter()
        required = len(t_counts)
        formed = 0

        l, r = 0, 0
        min_len = float('inf')
        min_window = ""

        while r < len(s):
            char = s[r]
            window_counts[char] += 1

            if char in t_counts and window_counts[char] == t_counts[char]:
                formed += 1

            while l <= r and formed == required:
                char = s[l]
                if r - l + 1 < min_len:
                    min_len = r - l + 1
                    min_window = s[l:r+1]

                window_counts[char] -= 1
                if char in t_counts and window_counts[char] < t_counts[char]:
                    formed -= 1

                l += 1

            r += 1

        return min_window

10 Prerequisite LeetCode Problems

“Minimum Window Substring” is a classic problem about using two pointers and a sliding window technique to solve substring problems. Here are 10 problems to prepare for it:

  1. “Two Sum” (LeetCode Problem #1): This is a simple problem using two pointers, which can help you understand the basic idea of two pointer method.

  2. “Reverse String” (LeetCode Problem #344): This problem will give you an understanding on how to manipulate two pointers on a string.

  3. “Maximum Subarray” (LeetCode Problem #53): This problem helps to understand the sliding window concept, though the window size isn’t variable in this case.

  4. “Subarray Sum Equals K” (LeetCode Problem #560): This problem is a step up from Maximum Subarray, as it introduces the concept of variable window size.

  5. “Find All Anagrams in a String” (LeetCode Problem #438): This problem is similar to Minimum Window Substring but simpler. It’s a good practice for using sliding window to check all substrings.

  6. “Longest Substring Without Repeating Characters” (LeetCode Problem #3): It is a fundamental problem to understand sliding window technique on strings.

  7. “Sliding Window Maximum” (LeetCode Problem #239): This problem involves a slightly more complex sliding window problem, where you have to keep track of the maximum in each window.

  8. “Permutation in String” (LeetCode Problem #567): This problem is similar to the Minimum Window Substring problem but is easier as it asks for a permutation (anagram), not a subset.

  9. “Longest Repeating Character Replacement” (LeetCode Problem #424): This problem introduces another complexity to the sliding window technique where you’re allowed to replace characters.

  10. “Fruit Into Baskets” (LeetCode Problem #904): This problem makes a good practice to understand the concept of maintaining a sliding window with certain restrictions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""
        needstr = collections.defaultdict(int)
        for ch in t:
            needstr[ch] += 1
        needcnt = len(t)
        res = (0, float('inf'))
        start = 0
        for end, ch in enumerate(s):
            if needstr[ch] > 0:
                needcnt -= 1
            needstr[ch] -= 1
            if needcnt == 0:
                while True:
                    tmp = s[start]
                    if needstr[tmp] == 0:
                        break
                    needstr[tmp] += 1
                    start += 1
                if end - start < res[1] - res[0]:
                    res = (start, end)
                needstr[s[start]] += 1
                needcnt += 1
                start += 1
        return '' if res[1] > len(s) else s[res[0]:res[1]+1]

Problem Classification

This problem requires finding the smallest window in a string containing all characters of another string. It involves analyzing substrings and their properties, hence Text Analysis / Substring Properties.

This problem asks for the smallest part in a text that contains all characters of another text. It’s about analyzing parts of a text and their properties, thus Text Analysis.

Language Agnostic Coding Drills

Let’s break down this code into smallest units of learning. The code is a solution to finding the minimum window in string s which contains all characters of string t.

  1. Understanding Basic Programming Concepts Understanding variables, basic data types (int, float, string), conditional statements and loops.

  2. Understanding Classes Understanding the basics of classes, methods and the self keyword in Python.

  3. Working with Strings Understanding how to manipulate and traverse strings in Python.

  4. Understanding collections.defaultdict Using defaultdict to handle missing keys in a dictionary.

  5. Understanding Enumerate Understanding the use of enumerate() for getting index/value pairs in a loop.

  6. Manipulating Dictionary Understanding how to add, remove, check elements in dictionary and how to use it to keep count of characters.

  7. Understanding if Conditions and Loops Understanding and using nested if conditions and loops in Python.

  8. Manipulating Lists Understanding list indexing, slicing and methods to add, remove elements from list.

  9. Understanding the Sliding Window Concept Using two pointers to create a window and adjust its size.

  10. Understanding and Implementing the Solution to the Problem Combining all of the above to understand and implement the solution to the problem.

Starting with basic programming concepts like variables, loops, and if conditions, we gradually move up in complexity to understanding classes, strings, dictionaries and then to more complex concepts like using collections.defaultdict, enumerate(), and understanding the sliding window concept in algorithms. Finally, we combine all these to understand and implement the solution to the problem.

Targeted Drills in Python

Let’s create some drills based on the concepts identified:

  1. Understanding Basic Programming Concepts Goal: Create a program that uses variables, basic data types, conditional statements, and loops.

    1
2
3
4
5

    number = 10
if number < 15:
    print("Number is less than 15.")
for i in range(5):
    print(i)

  2. Understanding Classes Goal: Define a simple class with a method.

    1
2
3
4
5

    class HelloWorld:
    def say_hello(self):
        print("Hello, world!")
hello_world = HelloWorld()
hello_world.say_hello()

  3. Working with Strings Goal: Manipulate and traverse a string.

    1
2
3
4

    s = "Hello, world!"
print(s.lower())
for char in s:
    print(char)

  4. Understanding collections.defaultdict Goal: Use defaultdict to handle missing keys in a dictionary.

    1
2
3

    from collections import defaultdict
d = defaultdict(int)
print(d["missing_key"])  # prints 0, the default value

  5. Understanding Enumerate Goal: Use enumerate to get index/value pairs in a loop.

    1
2
3

    lst = ["a", "b", "c"]
for index, value in enumerate(lst):
    print(index, value)

  6. Manipulating Dictionary Goal: Manipulate a dictionary to count the frequency of characters in a string.

    1
2
3
4
5
6
7
8

    s = "hello"
freq_dict = {}
for char in s:
    if char in freq_dict:
        freq_dict[char] += 1
    else:
        freq_dict[char] = 1
print(freq_dict)

  7. Understanding if Conditions and Loops Goal: Use nested if conditions and loops to find all even numbers in a 2D array.

    1
2
3
4
5

    arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for sub_arr in arr:
    for num in sub_arr:
        if num % 2 == 0:
            print(num)

  8. Manipulating Lists Goal: Use list indexing, slicing, and methods to manipulate a list.

    1
2
3
4
5

    lst = [1, 2, 3, 4, 5]
lst.append(6)
print(lst[0])  # prints 1
print(lst[-1])  # prints 6
print(lst[1:4])  # prints [2, 3, 4]

  9. Understanding the Sliding Window Concept Goal: Use the sliding window concept to find the maximum sum of any contiguous subarray of size k.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    def max_sum_subarray_size_k(arr, k):
    max_sum = float('-inf')
    window_sum = 0
    window_start = 0

    for window_end in range(len(arr)):
        window_sum += arr[window_end]
        if window_end >= k-1:
            max_sum = max(max_sum, window_sum)
            window_sum -= arr[window_start]
            window_start += 1
    return max_sum

print(max_sum_subarray_size_k([2, 1, 5, 1, 3, 2], 3))

  10. Understanding and Implementing the Solution to the Problem The goal for this drill would be to understand and implement the solution to the minimum window substring problem using the