Problem
Given two strings s and t, return the smallest substring of s that contains all the characters of t, including their frequencies. If no such substring exists, return an empty string.Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "ADOBECODEBANC"
t = "ABC" Output
"BANC" Solution
This solution uses the Sliding Window technique along with a HashMap to keep track of the required character frequencies.The right pointer expands the window by including characters until all required characters are present with the correct frequencies.
Once a valid window is found, the left pointer shrinks the window as much as possible while keeping it valid. During this process, the smallest valid window is continuously updated.
This approach ensures that each character is processed only a constant number of times.
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
Map<Character, Integer> map = new HashMap<>();
for (char c : t.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int left = 0;
int matched = 0;
int minStart = 0;
int minLength = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) >= 0) {
matched++;
}
}
while (matched == t.length()) {
if (right - left + 1 < minLength) {
minLength = right - left + 1;
minStart = left;
}
char leftChar = s.charAt(left);
if (map.containsKey(leftChar)) {
map.put(leftChar, map.get(leftChar) + 1);
if (map.get(leftChar) > 0) {
matched--;
}
}
left++;
}
}
return minLength == Integer.MAX_VALUE
? ""
: s.substring(minStart, minStart + minLength);
}
Complexity
The algorithm traverses the string using a sliding window, where each character is visited at most twice—once when expanding the window and once when shrinking it. Therefore, the overall time complexity isO(n). The HashMap stores the required frequencies of the characters in t, resulting in an extra space complexity of
O(m), where m is the number of distinct characters in t.