Finding the Smallest Window in a String: A Sliding Window Masterclass
As a seasoned software engineer specializing in algorithm design and optimization, I’ve spent years solving complex string manipulation problems.
One such problem is finding the smallest substring in a string `s` that contains all characters of another string `t.`
The sliding window technique comes in handy in this problem.
The solutions to most substring-related problems use this powerful strategy efficiently.
In this article, I’ll walk you through an optimized Python solution, breaking it down into simple, easy-to-understand steps.
Whether preparing for coding interviews or building real-world applications, this guide will help you master the sliding window approach.
The Problem: Minimum Window Substring
Given two strings, `s` and `t`, we need to find the smallest substring in `s` with all the characters of `t`. For example:
- If `s = "ADOBECODEBANC"` and `t = "ABC"`, the smallest window is `"BANC"`.
- If `s = "a"` and `t = "aa"`, there’s no valid window, so the answer is an empty string `""`.
A brute-force approach would involve checking all possible substrings of `s`, but this is highly inefficient, with a time complexity of O(N²).
Instead, we’ll solve this problem in O(N) time using the sliding window technique.
The Solution: Sliding Window with Frequency Counting
In the sliding window, we maintain a window that is a substring of `s`.
That window dynamically shrinks or expands depending on particular conditions at play.
Here’s how it works:
- Frequency Counters: We use two counters, `t_counter` and `s_counter`, to store the frequency of characters in `t` and the current window of `s`, respectively.
- Expand the Window: We expand the window by moving the right pointer (`r`) and adding characters to `s_counter`.
- Shrink the Window: Once the window contains all characters of `t`, we shrink it from the left (`l`) to find the smallest valid window.
- Track the Result: We keep track of the smallest valid window and return it at the end.
Here’s the optimized Python code with detailed comments and docstrings:
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
"""
Find the smallest substring in `s` that contains all characters of `t`.
Args:
s (str): The string to search within.
t (str): The string containing characters to match.
Returns:
str: The smallest valid window or an empty string if no valid window exists.
"""
# Base case: If `t` is longer than `s`, no valid window exists
if len(t) > len(s):
return ""
# If `s` and `t` are the same length, check if they match
if len(t) == len(s) and self.contains_all_chars(Counter(s), Counter(t)):
return s
l = 0 # Left pointer of the window
t_counter = Counter(t) # Frequency counter for `t`
s_counter = Counter() # Frequency counter for the current window in `s`
shortest_substr = "" # Stores the smallest valid window
s_len = float("inf") # Length of the smallest valid window
# Expand the window by moving the right pointer
for r in range(len(s)):
s_counter[s[r]] += 1 # Add the current character to `s_counter`
# Shrink the window if it contains all characters of `t`
while self.contains_all_chars(s_counter, t_counter):
win = s[l:r + 1] # Current window
# Update the smallest window if the current one is smaller
if len(win) < s_len:
s_len = len(win)
shortest_substr = win
# Shrink the window from the left
s_counter[s[l]] -= 1
if s_counter[s[l]] == 0:
del s_counter[s[l]] # Clean up to prevent unnecessary keys
l += 1
return shortest_substr
def contains_all_chars(self, s_counter, t_counter):
"""
Check if `s_counter` contains all characters of `t_counter`.
Args:
s_counter (Counter): Frequency counter for the current window in `s`.
t_counter (Counter): Frequency counter for `t`.
Returns:
bool: True if `s_counter` contains all characters of `t_counter`, False otherwise.
"""
return all(s_counter[char] >= count for char, count in t_counter.items())
Why This Approach Works
Efficiency
The sliding window ensures we traverse `s` only once. As a result, we have an O(N) complexity in time. Where N is the length of `s`.
Space Optimization
We use frequency counters to track characters, keeping the space complexity at O(M) where M is t's unique characters.
Dynamic-Window Adjustment
We realize the smallest valid substring efficiently without redundant checks. We do so by shrinking or expanding the window.
Alternative Approach
Here's a slight variation of the solution above, using a frequency counter.
from collections import Counter
def minimum_window_substring(s:str, t:str)->str:
"""
Given two strings s and t, return the minimum window in s that contains all characters in t.
Args:
s(str): a string
Returns:
str
Example:
>>>minimum_window_substring("ADOBECODEBANC","ABC")
BANC
"""
dp={}
for i in t:
dp[i]=dp.get(i,0) + 1
l=0
win=""
max_len=float("inf")
s_dp={}
for r in range(len(s)):
s_dp[s[r]]=s_dp.get(s[r],0)+1
while compare_dicts(dp, s_dp):
if len(s[l:r+1]) < max_len:
win =s[l:r+1]
s_dp[s[l]] -=1
if s_dp[s[l]]==0:
del s_dp[s[l]]
l +=1
return win
def compare_dicts(a_dict, b_dict):
"""
Compare two dictionaries and return True if all key-value pairs in a_dict
are present in b_dict with values greater than or equal.
Args:
a_dict(dict): dictionary to be checked against
b_dict(dict): dictionary whose characters will be checked
Returns:
bool: True if all characters in a_dict are in b_dict else False
Example:
>>> a = {'a': 2, 'b': 1}
>>> b = {'a': 3, 'b': 1, 'c': 5}
>>> compare_dicts(a, b)
True
>>> a = {'a': 4, 'b': 1}
>>> b = {'a': 3, 'b': 1, 'c': 5}
>>> compare_dicts(a, b)
False
"""
for key, value in a_dict.items():
# Check if key exists in b_dict and its value is >= value in a_dict
if key not in b_dict or b_dict[key] < value:
return False
return True
print("Expected: BANC, Actual:",minimum_window_substring("ADOBECODEBANC","ABC"))
Next Steps
Try out the following edge cases:
1) `t` > `s` situations.
2) Empty strings
3) Concatenation of substrings
4) Strings/substring with/without repeated characters (longest is also applicable)
So, what are you waiting for?
Start coding, experiment with the solution, and watch your problem-solving skills soar!