Minimum Window Substring
Program for Smallest Substring in a string that contains all the characters of another string Problem
You are given two strings, s and t. Your task is to find the smallest substring in s that contains all the characters of t, including their respective frequencies (i.e., duplicates must also be accounted for).
If no such substring exists, return an empty string (“”). You can assume that, if a valid substring exists, it will always be unique, meaning there won’t be multiple shortest substrings satisfying the condition.
Output: "YXAZ"
Explanation :“YXAZ” is the shortest substring that includes “X”, “Y”, and “Z” from string t.
Output: apzo
Explanation: “apzo” is the smallest substring in which “oza” can be found.
Constraints:
- 1 <= s1.length, s2.length <= 1000
Program for Smallest Substring in a string that contains all the characters of another string Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(n) time and O(m) space, where n is the length of the string s and m is the number of unique characters in s and t.
Hints for solving problems
Hint 1 :
A brute force solution would involve checking every substring of s against t and returning the minimum length valid substring. This would be an O(n^2) solution. Can you think of a better way? Maybe you should think in terms of frequency of characters.
Hint 2 :
We need to find substrings in s that should have atleast the characters of t. We can use hash maps to maintain the frequencies of characters. It will be O(1) for lookups. Can you think of an algorithm now?
There are mainly 2 approach to solve this problem-
- Brute Force Method
- Sliding Window Method
1. Brute Force Method
Generate all possible substrings of s and check if each contains all characters of t. Among valid substrings, return the shortest one. This approach is highly inefficient due to its exponential time complexity.
- Time complexity: O(n^2)
- Space complexity: O(m)
where n is the length of the string s and m is the total number of unique characters in the strings t and s.
Code
class Solution {
public:
string minWindow(string s, string t) {
if (t.empty()) return "";
unordered_map countT;
for (char c : t) {
countT[c]++;
}
pair res = {-1, -1};
int resLen = INT_MAX;
for (int i = 0; i < s.length(); i++) {
unordered_map countS;
for (int j = i; j < s.length(); j++) {
countS[s[j]]++;
bool flag = true;
for (auto &[c, cnt] : countT) {
if (countS[c] < cnt) {
flag = false;
break;
}
}
if (flag && (j - i + 1) < resLen) {
resLen = j - i + 1;
res = {i, j};
}
}
}
return resLen == INT_MAX ? "" : s.substr(res.first, resLen);
}
};
public class Solution {
public String minWindow(String s, String t) {
if (t.isEmpty()) return "";
Map countT = new HashMap<>();
for (char c : t.toCharArray()) {
countT.put(c, countT.getOrDefault(c, 0) + 1);
}
int[] res = {-1, -1};
int resLen = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); i++) {
Map countS = new HashMap<>();
for (int j = i; j < s.length(); j++) {
countS.put(s.charAt(j), countS.getOrDefault(s.charAt(j), 0) + 1);
boolean flag = true;
for (char c : countT.keySet()) {
if (countS.getOrDefault(c, 0) < countT.get(c)) {
flag = false;
break;
}
}
if (flag && (j - i + 1) < resLen) {
resLen = j - i + 1;
res[0] = i;
res[1] = j;
}
}
}
return resLen == Integer.MAX_VALUE ? "" : s.substring(res[0], res[1] + 1);
}
}
class Solution:
def minWindow(self, s: str, t: str) -> str:
if t == "":
return ""
countT = {}
for c in t:
countT[c] = 1 + countT.get(c, 0)
res, resLen = [-1, -1], float("infinity")
for i in range(len(s)):
countS = {}
for j in range(i, len(s)):
countS[s[j]] = 1 + countS.get(s[j], 0)
flag = True
for c in countT:
if countT[c] > countS.get(c, 0):
flag = False
break
if flag and (j - i + 1) < resLen:
resLen = j - i + 1
res = [i, j]
l, r = res
return s[l : r + 1] if resLen != float("infinity") else ""
class Solution {
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
minWindow(s, t) {
if (t === "") return "";
let countT = {};
for (let c of t) {
countT[c] = (countT[c] || 0) + 1;
}
let res = [-1, -1];
let resLen = Infinity;
for (let i = 0; i < s.length; i++) {
let countS = {};
for (let j = i; j < s.length; j++) {
countS[s[j]] = (countS[s[j]] || 0) + 1;
let flag = true;
for (let c in countT) {
if ((countS[c] || 0) < countT[c]) {
flag = false;
break;
}
}
if (flag && (j - i + 1) < resLen) {
resLen = j - i + 1;
res = [i, j];
}
}
}
return resLen === Infinity ? "" : s.slice(res[0], res[1] + 1);
}
}
2. Sliding Window Method
Use two pointers to create a dynamic window in s, expanding and contracting it to include all characters of t. Maintain a frequency map to track the characters and efficiently find the smallest valid window.
- Time complexity: O(n)
- Space complexity: O(m)
where n is the length of the string s and m is the total number of unique characters in the strings t and s.
Code
class Solution {
public:
string minWindow(string s, string t) {
if (t.empty()) return "";
unordered_map countT, window;
for (char c : t) {
countT[c]++;
}
int have = 0, need = countT.size();
pair res = {-1, -1};
int resLen = INT_MAX;
int l = 0;
for (int r = 0; r < s.length(); r++) {
char c = s[r];
window[c]++;
if (countT.count(c) && window[c] == countT[c]) {
have++;
}
while (have == need) {
if ((r - l + 1) < resLen) {
resLen = r - l + 1;
res = {l, r};
}
window[s[l]]--;
if (countT.count(s[l]) && window[s[l]] < countT[s[l]]) {
have--;
}
l++;
}
}
return resLen == INT_MAX ? "" : s.substr(res.first, resLen);
}
};
public class Solution {
public String minWindow(String s, String t) {
if (t.isEmpty()) return "";
Map countT = new HashMap<>();
Map window = new HashMap<>();
for (char c : t.toCharArray()) {
countT.put(c, countT.getOrDefault(c, 0) + 1);
}
int have = 0, need = countT.size();
int[] res = {-1, -1};
int resLen = Integer.MAX_VALUE;
int l = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
window.put(c, window.getOrDefault(c, 0) + 1);
if (countT.containsKey(c) && window.get(c).equals(countT.get(c))) {
have++;
}
while (have == need) {
if ((r - l + 1) < resLen) {
resLen = r - l + 1;
res[0] = l;
res[1] = r;
}
char leftChar = s.charAt(l);
window.put(leftChar, window.get(leftChar) - 1);
if (countT.containsKey(leftChar) && window.get(leftChar) < countT.get(leftChar)) {
have--;
}
l++;
}
}
return resLen == Integer.MAX_VALUE ? "" : s.substring(res[0], res[1] + 1);
}
}
class Solution:
def minWindow(self, s: str, t: str) -> str:
if t == "":
return ""
countT, window = {}, {}
for c in t:
countT[c] = 1 + countT.get(c, 0)
have, need = 0, len(countT)
res, resLen = [-1, -1], float("infinity")
l = 0
for r in range(len(s)):
c = s[r]
window[c] = 1 + window.get(c, 0)
if c in countT and window[c] == countT[c]:
have += 1
while have == need:
if (r - l + 1) < resLen:
res = [l, r]
resLen = r - l + 1
window[s[l]] -= 1
if s[l] in countT and window[s[l]] < countT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l : r + 1] if resLen != float("infinity") else ""
class Solution {
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
minWindow(s, t) {
if (t === "") return "";
let countT = {};
let window = {};
for (let c of t) {
countT[c] = (countT[c] || 0) + 1;
}
let have = 0, need = Object.keys(countT).length;
let res = [-1, -1];
let resLen = Infinity;
let l = 0;
for (let r = 0; r < s.length; r++) {
let c = s[r];
window[c] = (window[c] || 0) + 1;
if (countT[c] && window[c] === countT[c]) {
have++;
}
while (have === need) {
if ((r - l + 1) < resLen) {
resLen = r - l + 1;
res = [l, r];
}
window[s[l]]--;
if (countT[s[l]] && window[s[l]] < countT[s[l]]) {
have--;
}
l++;
}
}
return resLen === Infinity ? "" : s.slice(res[0], res[1] + 1);
}
}
