Minimum Window Substring in DSA Python - Build from Scratch

Minimum Window Substring

📖 Scenario: Imagine you are working on a text analysis tool that needs to find the smallest part of a document containing all the keywords a user is searching for. This helps users quickly find the most relevant snippet without reading the entire text.

🎯 Goal: Build a program that finds the minimum window substring in a given string s that contains all the characters of another string t. The program should return the smallest substring of s that includes every character in t at least once.

📋 What You'll Learn

Create a string variable s with the value "ADOBECODEBANC".

Create a string variable t with the value "ABC".

Create a dictionary called dict_t that counts the frequency of each character in t.

Create variables required, formed, l, r, window_counts, ans to help find the minimum window substring.

Use a while loop to expand the right pointer r over s and update counts.

Use a nested while loop to contract the left pointer l when the current window contains all characters of t.

Print the minimum window substring found or an empty string if no such window exists.

💡 Why This Matters

🌍 Real World

Finding the shortest snippet in a document that contains all search keywords helps users quickly locate relevant information.

💼 Career

This technique is useful in search engines, text editors, and any software that needs efficient substring searching.

1

Create the input strings

Create a string variable called s with the value "ADOBECODEBANC" and another string variable called t with the value "ABC".

DSA Python

# Create the input strings s and t
# Your code here

Hint

Use simple assignment to create the two strings exactly as given.

2

Count characters in t

Create a dictionary called dict_t that counts how many times each character appears in the string t. Use a dictionary comprehension or a loop.

DSA Python

s = "ADOBECODEBANC"
t = "ABC"
# Create dict_t to count characters in t
# Your code here

Hint

Loop over each character in t and update the count in dict_t.

3

Initialize variables for sliding window

Create variables: required as the number of unique characters in dict_t, formed as 0, l and r as 0, window_counts as an empty dictionary, and ans as a tuple (float('inf'), None, None).

DSA Python

s = "ADOBECODEBANC"
t = "ABC"
dict_t = {}
for char in t:
    dict_t[char] = dict_t.get(char, 0) + 1
# Initialize variables required, formed, l, r, window_counts, ans
# Your code here

Hint

Set up all variables needed to track the window and counts.

4

Find and print the minimum window substring

Use a while loop to move the right pointer r over s. Update window_counts for each character. If the count matches dict_t, increase formed. Then use a nested while loop to move the left pointer l to try to minimize the window while formed == required. Update ans with the smallest window found. After the loops, print the substring of s from ans[1] to ans[2] if ans[0] is not infinity; otherwise print an empty string.

DSA Python

s = "ADOBECODEBANC"
t = "ABC"
dict_t = {}
for char in t:
    dict_t[char] = dict_t.get(char, 0) + 1

required = len(dict_t)
formed = 0
l, r = 0, 0
window_counts = {}
ans = (float('inf'), None, None)
# Use while loops to find the minimum window substring
# Your code here

Hint

Use two pointers to expand and contract the window. Update counts and track the smallest valid window.