The Minimum Window Substring is a popular problem in computer science, especially in coding interviews. It combines string manipulation with efficient algorithms, making it both challenging and rewarding to solve. In this post, we’ll break down the problem and its key aspects to set a strong foundation before diving into solutions.
Step 1: Understand the Problem
To tackle the Minimum Window Substring problem, it’s critical to understand the requirements and constraints clearly. Let’s start with the essentials.
You are given two strings:
• s: The source string in which you need to find a substring.
• t: The target string whose characters must be included in the substring of s.
Objective:
Find the smallest substring of s that contains all characters of t, including duplicates. If no such substring exists, return an empty string.
Key Characteristics
• Order Does Not Matter:
• The order of characters in t doesn’t have to match their order in the substring of s.
• For example, if t = “ABC”, a valid substring could be “BANC”, “CAB”, or “BAC”, as long as all characters are included.
• Counts Do Matter:
• The substring must include all characters of t with the correct counts.
• If t = “AA”, then the substring must have at least two As.
• Return an Empty String if No Valid Substring Exists:
• For example, if t = “ABC” but s doesn’t contain C, the result is “”.
Step 2: Analyze Naive Solution
The brute force approach involves exhaustively generating and checking all substrings of s. Here’s how it works:
public class MinimumWindowSubstring {
public static String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
String result = "";
int minLength = Integer.MAX_VALUE;
// Generate all substrings
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
// Extract substring from i to j
String substring = s.substring(i, j + 1);
// Check if it contains all characters of t
if (containsAllChars(substring, t)) {
// Update the result if this substring is smaller
if (substring.length() < minLength) {
minLength = substring.length();
result = substring;
}
}
}
}
return result;
}
// Helper function to check if the substring contains all characters of t
private static boolean containsAllChars(String substring, String t) {
int[] tFreq = new int[128]; // Frequency array for t
int[] subFreq = new int[128]; // Frequency array for substring
// Count characters in t
for (char c : t.toCharArray()) {
tFreq[c]++;
}
// Count characters in the substring
for (char c : substring.toCharArray()) {
subFreq[c]++;
}
// Check if all characters in t are present in the substring with required frequency
for (char c : t.toCharArray()) {
if (subFreq[c] < tFreq[c]) {
return false;
}
}
return true;
}
}1. Generate All Substrings:
• Iterate over all possible start (i) and end (j) indices of s to extract every substring:
2. Check Each Substring:
• For each generated substring, check if it contains all characters of t:
• Count the frequency of each character in the substring.
• Compare the counts with the required frequency of characters in t.
• The validation step involves iterating over the substring and the characters of t, making it an O(n) operation per substring.
3. Keep Track of the Smallest Valid Substring:
• If a substring contains all characters of t, compare its length to the current smallest valid substring and update accordingly.
Mastering the Sliding Window Technique for Minimum Window Substring
The Minimum Window Substring problem is a perfect example of when to use the sliding window technique. This method provides an efficient way to solve problems that involve finding subsets or patterns in sequences. Now we’ll focus on the concept of a dynamic window, how two pointers are used to manage it, and the importance of tracking character frequencies
To efficiently solve the Minimum Window Substring problem, we leverage three core ideas:
1. Fixed vs. Dynamic Window
In the sliding window technique, the window represents a subset of the data we are examining. For this problem, the window corresponds to a substring of s that we adjust dynamically to meet the requirements of t.
• Fixed Window:
• A fixed window has a predetermined size that remains constant as it slides across the sequence.
• This is useful for problems like finding the average of all subarrays of size k.
• Dynamic Window:
• In this problem, we use a dynamic window where the size can grow or shrink as needed.
• The window expands to include characters from s until it satisfies the condition (contains all characters of t).
• Once the condition is met, the window shrinks to find the smallest valid substring.
2. Two Pointers
Two pointers are the backbone of the sliding window approach. They define and manage the boundaries of the current window.
• Right Pointer (r):
• The right pointer is responsible for expanding the window.
• As r moves to the right, characters are added to the window, making it larger.
• Left Pointer (l):
• The left pointer is responsible for shrinking the window.
• Once the window satisfies the condition (contains all characters of t), move l to the right to minimize the window size.
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
// Frequency map for characters in t
Map<Character, Integer> required = new HashMap<>();
for (char c : t.toCharArray()) {
required.put(c, required.getOrDefault(c, 0) + 1);
}
// Variables for the sliding window
Map<Character, Integer> windowCounts = new HashMap<>();
int l = 0, r = 0;
int formed = 0; // Number of characters in the window that meet the required frequency
int requiredCount = required.size();
int minLength = Integer.MAX_VALUE;
int start = 0;
while (r < s.length()) {
char c = s.charAt(r);
windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
if (required.containsKey(c) && windowCounts.get(c).intValue() == required.get(c).intValue()) {
formed++;
}
while (formed == requiredCount) {
if (r - l + 1 < minLength) {
minLength = r - l + 1;
start = l;
}
char leftChar = s.charAt(l);
windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
if (required.containsKey(leftChar) && windowCounts.get(leftChar) < required.get(leftChar)) {
formed--;
}
l++;
}
r++;
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
}Step-By-Step Explanation
- Frequency Map For Characters in t
Map<Character, Integer> required = new HashMap<>();
for (char c : t.toCharArray()) {
required.put(c, required.getOrDefault(c, 0) + 1);
}• A frequency map (required) tracks the count of each character in t.
• Example:
• If t = “ABC”, then required = {A: 1, B: 1, C: 1}.
• If t = “AAB”, then required = {A: 2, B: 1}.
This ensures the algorithm knows the exact number of each character required in the substring.
