Here, We see Minimum Window Substring LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Minimum Window Substring LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Minimum Window Substring LeetCode Solution
Table of Contents
Problem Statement
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.
Example 1: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. Example 2: Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window. Example 3: 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.
Minimum Window Substring Leetcode Solution C++
class Solution {
public:
string minWindow(string s, string t) {
int m=s.size(), n=t.size();
unordered_map<char, int> mp;
int ans = INT_MAX;
int start = 0;
for(auto x:t)
mp[x]++;
int count = mp.size();
int i = 0, j = 0;
while (j < s.length()) {
mp[s[j]]--;
if (mp[s[j]] == 0)
count--;
if (count == 0) {
while (count == 0) {
if (ans > j - i + 1) {
ans = j - i + 1;
start = i;
}
mp[s[i]]++;
if (mp[s[i]] > 0)
count++;
i++;
}
}
j++;
}
if (ans != INT_MAX)
return s.substr(start, ans);
else
return "";
}
};
Code language: PHP (php)
Minimum Window Substring Leetcode Solution Java
class Solution {
public String minWindow(String s, String t) {
char[] needToFind = new char[256];
char[] hasFound = new char[256];
int sLen = s.length();
int tLen = t.length();
int count = 0;
int optLen = Integer.MAX_VALUE; // opt stands for optimal
int optBegin = 0;
int optEnd = 0;
for (int i = 0; i < tLen; i++) { // gives a counter for each character in t
needToFind[t.charAt(i)]++;
}
for (int begin = 0, end = 0; end < sLen; end++) {
if (needToFind[s.charAt(end)] == 0) { // skips irrelevant char
continue;
}
char currEnd = s.charAt(end); // the char at the end
hasFound[currEnd]++;
if (hasFound[currEnd] <= needToFind[currEnd]) {
count++;
}
if (count == tLen) { // pauses end, moves beginning to the right as much as possible
char currBegin = s.charAt(begin); // char at begin
while (hasFound[currBegin] > needToFind[currBegin] || needToFind[currBegin] == 0) {
if (hasFound[currBegin] > needToFind[currBegin]) {
hasFound[currBegin]--;
}
begin++;
currBegin = s.charAt(begin);
}
if (optLen > end - begin + 1) { // if current length is smaller, update our optimum solution
optLen = end - begin + 1;
optBegin = begin;
optEnd = end;
}
}
}
if (count != tLen) {
return "";
}
return s.substring(optBegin, optEnd + 1);
}
}
Code language: JavaScript (javascript)
Minimum Window Substring Leetcode Solution JavaScript
var minWindow = function(s, t) {
let min = "", left = 0, right = -1;
let map = {};
t.split('').forEach(element => {
if (map[element]==null) map[element] = 1;
else map[element] = map[element] + 1;
});
let count = Object.keys(map).length;
while (right <= s.length) {
if (count == 0) {
let current = s[left];
if (map[current] != null) map[current]++;
if (map[current] > 0) count++;
let temp = s.substring(left, right+1)
if (min == "") min = temp;
else min = min.length<temp.length?min:temp;
left++;
} else {
right++;
let current = s[right];
if (map[current] != null) map[current]--;
if (map[current] == 0) count--;
}
}
return min;
};
Code language: JavaScript (javascript)
Minimum Window Substring Leetcode Solution Python
class Solution(object):
def minWindow(self, s, t):
need, missing = collections.Counter(t), len(t)
i = I = J = 0
for j, c in enumerate(s, 1):
missing -= need[c] > 0
need[c] -= 1
if not missing:
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
if not J or j - i <= J - I:
I, J = i, j
return s[I:J]