Given two strings, s (the main string) and t (the pattern), find the smallest window in s that contains all the characters of t. If there is no such window in s, return an empty string.
Input/Output Examples
plaintext
Example 1:
Input:
s = "ADOBECODEBANC"
t = "ABC"
Output: "BANC"
Explanation: The smallest window in s that contains all characters of t is "BANC".
Example 2:
Input:
s = "a"
t = "aa"
Output: ""
Explanation: The main string s does not contain all characters of t.
Example 3:
Input:
s = "this is a test string"
t = "tist"
Output: "t stri"
Explanation: The smallest window in s that contains all characters of t is "t stri".
Approach to Find the Smallest Window in a String Containing All Characters of Another String
- Use Two Pointers and a Sliding Window:
- Initialize two pointers, both starting at the beginning of the string
s, to define the current window.
- Initialize two pointers, both starting at the beginning of the string
- Create Frequency Counters for Characters in
**t**and in the Current Window:- Use a hash map or array to store the frequency of characters in
tand another to track the frequency of characters within the current window ins.
- Use a hash map or array to store the frequency of characters in
- Expand the Window to Find a Valid Window:
- Move the right pointer to expand the window until it contains all characters of
tin the required frequency.
- Move the right pointer to expand the window until it contains all characters of
- Shrink the Window to Find the Smallest Valid Window:
- Once a valid window is found, try to minimize the window by moving the left pointer to the right while still maintaining the validity of the window.
- Track the Minimum Window:
- Keep track of the minimum length of the window that contains all characters of
tand update the result accordingly.
- Keep track of the minimum length of the window that contains all characters of
C++ Program to Find the Smallest Window in a String Containing All Characters of Another String
cpp
#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;
// Function to find the smallest window containing all characters of t
string minWindow(const string& s, const string& t) {
unordered_map<char, int> tFreq;
for (char c : t) tFreq[c]++;
int left = 0, right = 0, count = 0;
int minLength = INT_MAX, minStart = 0;
unordered_map<char, int> windowFreq;
while (right < s.size()) {
char rChar = s[right];
if (tFreq.find(rChar) != tFreq.end()) {
windowFreq[rChar]++;
if (windowFreq[rChar] <= tFreq[rChar]) count++;
}
while (count == t.size()) {
if (right - left + 1 < minLength) {
minLength = right - left + 1;
minStart = left;
}
char lChar = s[left];
if (tFreq.find(lChar) != tFreq.end()) {
if (windowFreq[lChar] == tFreq[lChar]) count--;
windowFreq[lChar]--;
}
left++;
}
right++;
}
return minLength == INT_MAX ? "" : s.substr(minStart, minLength);
}
int main() {
string s = "ADOBECODEBANC";
string t = "ABC";
cout << "Smallest window: " << minWindow(s, t) << endl;
return 0;
}
Java Program to Find the Smallest Window in a String Containing All Characters of Another String
java
import java.util.HashMap;
public class SmallestWindowSubstring {
// Function to find the smallest window containing all characters of t
public static String minWindow(String s, String t) {
HashMap<Character, Integer> tFreq = new HashMap<>();
for (char c : t.toCharArray()) {
tFreq.put(c, tFreq.getOrDefault(c, 0) + 1);
}
int left = 0, count = 0, minLength = Integer.MAX_VALUE;
int minStart = 0;
HashMap<Character, Integer> windowFreq = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char rChar = s.charAt(right);
if (tFreq.containsKey(rChar)) {
windowFreq.put(rChar, windowFreq.getOrDefault(rChar, 0) + 1);
if (windowFreq.get(rChar) <= tFreq.get(rChar)) count++;
}
while (count == t.length()) {
if (right - left + 1 < minLength) {
minLength = right - left + 1;
minStart = left;
}
char lChar = s.charAt(left);
if (tFreq.containsKey(lChar)) {
if (windowFreq.get(lChar).equals(tFreq.get(lChar))) count--;
windowFreq.put(lChar, windowFreq.get(lChar) - 1);
}
left++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLength);
}
public static void main(String[] args) {
String s = "this is a test string";
String t = "tist";
System.out.println("Smallest window: " + minWindow(s, t));
}
}
Python Program to Find the Smallest Window in a String Containing All Characters of Another String
python
from collections import Counter
# Function to find the smallest window containing all characters of t
def min_window(s, t):
t_freq = Counter(t)
window_freq = {}
left = 0
count = 0
min_length = float('inf')
min_start = 0
for right, char in enumerate(s):
if char in t_freq:
window_freq[char] = window_freq.get(char, 0) + 1
if window_freq[char] <= t_freq[char]:
count += 1
while count == len(t):
if right - left + 1 < min_length:
min_length = right - left + 1
min_start = left
l_char = s[left]
if l_char in t_freq:
if window_freq[l_char] == t_freq[l_char]:
count -= 1
window_freq[l_char] -= 1
left += 1
return "" if min_length == float('inf') else s[min_start:min_start + min_length]
# Example usage
if __name__ == "__main__":
s = "ADOBECODEBANC"
t = "ABC"
print("Smallest window:", min_window(s, t))
- Time Complexity:
O(n), wherenis the length of the strings, as each character is processed at most twice (once when expanding and once when contracting the window). - Space Complexity:
O(1)with respect to the character set, assuming a limited character set like ASCII, since the frequency counters are limited to the characters int.
