In the Leetcode Minimum Window Substring problem solution 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.
Constraints:
- m == s.length
- n == t.length
- 1 <= m, n <= 105
- s and t consist of uppercase and lowercase English letters.
Solution in C Programming
char * minWindow(char * s, char * t){
int map[256] = {0};
int start =0;
int end = 0;
int missing = strlen (t);
int minWindow = -1;
int minwindowstart = -1;
int curwindow = 0;
for (int i = 0; i< missing;i++)
{
map[t[i]]++;
}
//printf("debug1 %d \n",debug1);
while(end < strlen(s))
{
if(map[s[end]] > 0)
{
missing--;
}
//let the count become negative for other cases
map[s[end]]--;
while(missing == 0)
{
curwindow = end -start + 1;
//printf("curwindow %d end %d start %d\n",curwindow,end,start);
if ((minWindow == -1) || (curwindow < minWindow))
{
minWindow = curwindow;
minwindowstart = start;
//printf("window size of answer%d\n",minWindow);
}
if(map[s[start]] >= 0)
{
missing++;
}
map[s[start]]++;
start++;
}
end++;
}
if(minWindow == -1)
return "";
// we have the begin and length of window
//printf("FINAL window size of answer%d start %d end %d minwindowstart %d\n",minWindow,start,end,minwindowstart);
char *str = malloc (sizeof(char)*(minWindow + 1));
int j = 0;
for(int i = minwindowstart; j<minWindow;j++)
{
str[j] = s[i];
i++;
}
str[j] = '\0';
return str;
}Solution in C++ Programming
class Solution {
public:
string minWindow(string str, string pat)
{
int len1 = str.length();
int len2 = pat.length();
if (len1 < len2)
return "";
int hash_pat[256] = { 0 };
int hash_str[256] = { 0 };
for (int i = 0; i < len2; i++)
hash_pat[pat[i]]++;
int start = 0, start_index = -1, min_len = INT_MAX;
int count = 0;
for (int j = 0; j < len1; j++)
{
hash_str[str[j]]++;
if (hash_str[str[j]] <= hash_pat[str[j]])
count++;
if (count == len2)
{
while (hash_str[str[start]] > hash_pat[str[start]] || hash_pat[str[start]] == 0)
{
if (hash_str[str[start]] > hash_pat[str[start]])
hash_str[str[start]]--;
start++;
}
int len_window = j - start + 1;
if (min_len > len_window)
{
min_len = len_window;
start_index = start;
}
}
}
// If no window found
if (start_index == -1)
return "";
return str.substr(start_index, min_len);
}
};Solution in Java Programming
class Solution {
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 start = 0;
int end = 0;
int count = 0;
int min = s.length() + 1;
String res = "";
while (end < s.length()) {
while (end < s.length() && count < t.length()) {
char c = s.charAt(end);
if (map.containsKey(c)) {
if (map.get(c) > 0) {
count++;
}
map.put(c, map.get(c) - 1);
}
end++;
}
while (count >= t.length()) {
if (end - start < min) {
min = end - start;
res = s.substring(start, end);
}
char c = s.charAt(start);
if (map.containsKey(c)) {
if (map.get(c) >= 0) {
count--;
}
map.put(c, map.get(c) + 1);
}
start++;
}
}
return res;
}
}Solution in Python Programming
from collections import Counter
class Solution:
def minWindow(self, s, t):
# boundaries of the window
left_i = right_i = 0
# these 2 are used to get the window substring from string s
min_window_size = len(s) + 1
window_start_i = 0
# keeps track of the count of each character in string t
char_freq = Counter(t)
# keeps track of how much characters from t still need to be
# found in current string s window to make the window 'desirable'
# (contain all the chars in t)
num_chars_left = len(t)
while right_i < len(s):
# if character in string s is in string t
if char_freq[s[right_i]] > 0:
num_chars_left -= 1
# if the value becomes negative, that means the current
# character is not in string t (count would have previously
# been 0 since it was not in string t)
char_freq[s[right_i]] -= 1
right_i += 1
# if the current string s window is desirable
# try to make window smaller while keeping desirability
while num_chars_left == 0:
# if this is the smalest desirable window we've found so far,
# update window variables
if right_i - left_i < min_window_size:
min_window_size = right_i - left_i
window_start_i = left_i
# if count <= 0, the character is not in string t
# and we can continue making this desirable window smaller
# if count > 0, the character is in string t (aka window
# is no longer desirable) and we need to go back to the
# outer loop
char_freq[s[left_i]] += 1
if char_freq[s[left_i]] > 0:
num_chars_left += 1
left_i += 1
if min_window_size == len(s) + 1:
return ''
return s[window_start_i: window_start_i + min_window_size]Solution in C# Programming
public class Solution {
public string MinWindow(string s, string t) {
if(s.Length < t.Length ) return string.Empty;
Dictionary<char, int> map = new();
Dictionary<char, int> currMap = new();
InitializeMap(map, currMap, t);
int have = 0;
int need = map.Keys.Count();
bool flag = false; // this to check for edge case where length is one
int left = 0;
int right = 0;
int aleft = 0;
int aright = 0;
int min = s.Length;
while (right < s.Length)
{
if (currMap.ContainsKey(s[right]))
{
currMap[s[right]]++;
if (currMap[s[right]] == map[s[right]])
{
have++;
}
}
while (have == need)
{
flag = true; // It means atleat one answer is possible
int len = right - left + 1;
if (len <= min)
{
min = len;
aleft = left;
aright = right;
}
if (currMap.ContainsKey(s[left]))
{
currMap[s[left]]--;
if (currMap[s[left]] < map[s[left]])
have--;
}
left++;
}
right++;
}
string ans = "";
if (flag)
{
for (int i = aleft; i <= aright; i++)
{
ans += s[i];
}
}
return ans;
}
public static void InitializeMap(Dictionary<char, int> map, Dictionary<char, int> currMap, string t)
{
for (int i = 0; i < t.Length; i++)
{
if (!map.ContainsKey(t[i]))
map[t[i]] = 0;
map[t[i]]++;
currMap[t[i]] = 0;
}
}
}Also read,