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);
}
}
More Articles
Minimum Window Substring Leetcode Solution
Minimum Window Substring Leetcode Problem :
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string ” “.
The testcases will be generated such that the answer is unique.
Minimum Window Substring Leetcode Problem Solution :
Constraints :
- m == s.length
- n == t.length
- 1 <= m, n <= 105
- s and t consist of uppercase and lowercase English letters.
Example 1:
- Input: s = “a”, t = “aa”
- Output: “”
- Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.
Example 2:
- Input: s = “a”, t = “a”
- Output: “a”
- Explanation: The entire string s is the minimum window.
Idea to solve:
The problem asks to find the minimum window in s that contains all the characters of t. One way to approach this problem is to use a sliding window technique. We can maintain a window that starts from the beginning of s and moves forward until it contains all the characters of t. Once we have such a window, we can try to shrink it by moving the window’s start pointer forward while still keeping all the characters of t in the window. This will give us the minimum window.
Approach:
- Check if s is shorter than t. If it is, there is no possible solution, and we return an empty string.
- Create a frequency map of characters in t.
- Initialize count, start, min_length, and min_start to 0.
- Traverse the string s using the end pointer.
- If the current character in s is present in the frequency map, increment the count.
- Decrement the frequency of the current character in the frequency map.
- If the count equals the length of t, it means we have found a window that contains all characters of t. Now we try to shrink the window by moving the start pointer forward until the window still contains all the characters of t.
- If the length of the current window is smaller than the minimum length so far, update the minimum length and the minimum start.
- Increment the frequency of the character at the start pointer and decrement the count.
- Return the minimum window or an empty string if no window exists.
Complexity:
Time complexity: O(N), where N is the length of the string s.
We traverse the string s once.Space complexity: O(M), where M is the length of the string t.
We create a frequency map of characters in t.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
string minWindow(string s, string t) {
if(s.size() < t.size()){
return "";
}
unordered_map< char,int> map;
for(int i=0;i < t.size();i++){
map[t[i]]++;
}
int count=0,start=0,min_length = INT_MAX, min_start = 0;
for(int end=0; end< s.size(); end++){
if(map[s[end]]>0){
count++;
}
map[s[end]]--;
if(count == t.length()) {
while(start < end && map[s[start]] < 0){
map[s[start]]++, start++;
}
if(min_length > end-start){
min_length = end-(min_start=start)+1;
}
map[s[start++]]++;
count--;
}
}
return min_length == INT_MAX ? "" : s.substr(min_start, min_length);
}
};
class Solution {
public String minWindow(String s, String t) {
if(s.length() < t.length()){
return "";
}
Map< Character,Integer> map = new HashMap<>();
for(int i=0;i < t.length();i++){
map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
}
int count=0,start=0,min_length = Integer.MAX_VALUE, min_start = 0;
for(int end=0; end < s.length(); end++){
if(map.containsKey(s.charAt(end))){
if(map.get(s.charAt(end))>0){
count++;
}
map.put(s.charAt(end), map.get(s.charAt(end))-1);
}
if(count == t.length()) {
while(start < end && (!map.containsKey(s.charAt(start)) || map.get(s.charAt(start)) < 0)){
if(map.containsKey(s.charAt(start))){
map.put(s.charAt(start), map.get(s.charAt(start))+1);
}
start++;
}
if(min_length > end-start+1){
min_length = end-(min_start=start)+1;
}
if(map.containsKey(s.charAt(start))){
map.put(s.charAt(start), map.get(s.charAt(start))+1);
}
count--;
start++;
}
}
return min_length == Integer.MAX_VALUE ? "" : s.substring(min_start, min_start+min_length);
}
}class Solution(object):
def minWindow(self, s, t):
if len(s) < len(t):
return ""
map = {}
for char in t:
if char in map:
map[char] += 1
else:
map[char] = 1
count = 0
start = 0
min_length = float("inf")
min_start = 0
for end in range(len(s)):
if s[end] in map:
map[s[end]] -= 1
if map[s[end]] >= 0:
count += 1
while count == len(t):
if min_length > end - start + 1:
min_length = end - start + 1
min_start = start
if s[start] in map:
map[s[start]] += 1
if map[s[start]] > 0:
count -= 1
start += 1
return "" if min_length == float("inf") else s[min_start:min_start+min_length]
Login/Signup to comment