Imagine you’re given two strings: s (the source string) and t (the target string). Your task is to find the smallest substring of s that contains all the characters of t, including duplicates. This is like finding the shortest “highlighted” section in s that contains all the letters in t.
For example:
• Input: s = “ADOBECODEBANC”, t = “ABC”
• Output: “BANC”
This problem is tricky because it’s not just about finding characters but finding the smallest window that satisfies the condition.
Brute Force Approach
1. Generate All Substrings: For each starting index i in s, create all substrings ending at j and check if they contain all characters of t.
2. Check Character Inclusion: Use a helper function to verify if the substring contains all characters from t using a frequency array.
3. Track Minimum Length: If a valid substring is found, compare its length with the current minimum and update the result.
public class MinimumWindowSubstring {
public String minWindow(String s, String t) {
int minLength = Integer.MAX_VALUE;
String result = "";
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
String substring = s.substring(i, j + 1);
if (containsAllCharacters(substring, t)) {
if (substring.length() < minLength) {
minLength = substring.length();
result = substring;
}
}
}
}
return result;
}
private boolean containsAllCharacters(String s, String t) {
int[] count = new int[128];
for (char c : t.toCharArray()) count[c]++;
for (char c : s.toCharArray()) count[c]--;
for (int n : count) if (n > 0) return false;
return true;
}
}• Time Complexity: O(n^3) because:
• Generating substrings takes O(n^2).
• Verifying each substring takes O(n).
• Space Complexity: O(1) additional space, but inefficient due to redundant checks.
Optimized Approach
The problem requires finding the smallest substring in s that contains all characters from t (with their respective frequencies). This involves:
• Dynamically checking substrings of s.
• Validating whether a substring satisfies the condition of containing all characters in t.
• Minimizing the substring length.
The sliding window technique is ideal for problems involving contiguous subarrays or substrings because it dynamically adjusts the range being considered:
• A start pointer (left) marks the beginning of the current window.
• An end pointer (right) expands the window to include new characters.
A frequency counter is necessary because t specifies which characters and how many of each must be present in a valid window:
• An array charCount[128] is used to track the frequency of each character in t.
• As characters from s are added to the current window, the algorithm checks whether the window satisfies the frequency requirements of t.
public class Solution {
public String minWindow(String s, String t) {
int[] charCount = new int[128];
for (char c : t.toCharArray()) charCount[c]++;
int left = 0, minLength = Integer.MAX_VALUE, start = 0, matches = 0;
for (int right = 0; right < s.length(); right++) {
//check if char exists in charCount. also, decrease the count and increment matches.
if (charCount[s.charAt(right)]-- > 0) matches++;
while (matches == t.length()) {
if (right - left + 1 < minLength) {
minLength = Math.min(minLength, right - left + 1);
start = left;
}
if (++charCount[s.charAt(left++)] > 0) matches--;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
}
}Step 1: Initialize charCount
int[] charCount = new int[128];
for (char c : t.toCharArray()) charCount[c]++;• Tracks how many of each character in t is required to form a valid window.
• Using an array for ASCII characters ensures fast access (O(1) lookup).
Step 2: Initialize Sliding Window Variables
int left = 0, minLength = Integer.MAX_VALUE, start = 0, matches = 0;• left: Marks the start of the sliding window.
• minLength: Stores the length of the smallest valid window found so far.
• start: The starting index of the smallest valid window.
• matches: Tracks the number of characters in the window that satisfy the frequency requirements.
Step 3: Expand the Window
for (int right = 0; right < s.length(); right++) {
if (charCount[s.charAt(right)]-- > 0) matches++;
}- Iterates through the string s using the right pointer.
- Decrements the count of the current character in charCount.
Step 4: Shrink the Window
while (matches == t.length()) {
if (right - left + 1 < minLength) {
minLength = Math.min(minLength, right - left + 1);
start = left;
}
if (++charCount[s.charAt(left++)] > 0) matches--;
}- If all required characters are present the current window is valid.
- If the current window is smaller than minLength, update minLength and start.
- Move the left pointer to shrink the window, adjusting charCount and matches.
- The goal is to find the smallest valid window. Shrinking ensures we eliminate unnecessary characters while maintaining validity.
Step 5: Return
return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);• Checks if a valid window was found (minLength != Integer.MAX_VALUE).
• Returns the substring corresponding to the smallest valid window.
Conclusion
This algorithm demonstrates the sliding window pattern combined with a frequency counter for dynamic tracking of required characters. By expanding and shrinking the window dynamically, it efficiently finds the smallest valid substring. Its clean, linear design makes it an excellent example of optimal algorithmic practice for substring problems.
