# Solution For Minimum Window Substring

The Minimum Window Substring problem is a famous problem on LeetCode that requires you to find the smallest window in a string that contains all the characters of another string. This problem can be solved using a sliding window technique and hashing.

Here is a detailed solution on how to solve the Minimum Window Substring problem on LeetCode:

Step 1: Initialize two hash tables

• One hash table will store the frequency of each character in target string.
• The other hash table will store the frequency of each character in the sliding window.

Step 2: Determine the length of the target string.

• This step is important as we will use it later to check if we have found the minimum substring.

Step 3: Traverse the string.

• For each character, update the frequency of that character in the sliding window hash table.
• Check if the current sliding window contains all the characters of the target string.
• If yes, move the start index of the sliding window until we have the minimum window that contains all the characters of the target string.
• If no, continue to slide the window and update the frequency of characters until we find a window that contains all the characters.

Step 4: Return the minimum window.

• If a minimum window is found, return it. Otherwise, return an empty string.

Here is the Python implementation of the above algorithm:

“`
def minWindow(s, t):
target = {}
window = {}

``````for ch in t:
target[ch] = target.get(ch, 0) + 1

left, correct, right, result = 0, 0, 0, ""
while right<len(s):
ch = s[right]
if ch in target:
window[ch] = window.get(ch, 0) + 1
if window[ch] == target[ch]:
correct += 1

while correct == len(target):
if not result or right-left+1<len(result):
result = s[left:right+1]
ch = s[left]
if ch in target:
window[ch] -= 1
if window[ch] < target[ch]:
correct -= 1
left += 1

right += 1

return result
``````

“`

In the above implementation, we first initialize two hash tables for target and window and then calculate the length of target. We then traverse the string and update the frequency of characters in the window hash table and check if we have found all the characters of the target string. If we have found all characters, we move the start index of the window until we have found the minimum window. Finally, we return the minimum window that contains all the characters of the target string.

## Step by Step Implementation For Minimum Window Substring

```public class Solution {
public String minWindow(String s, String t) {
if(s == null || s.length() == 0 || t == null || t.length() == 0)
return "";

//create a map to save the characters in t
Map map = new HashMap<>();
for(int i = 0; i < t.length(); i++){
char c = t.charAt(i);
if(map.containsKey(c)){
map.put(c, map.get(c)+1);
}else{
map.put(c, 1);
}
}

//maintain a counter to check whether match all characters in t
int count = 0;
//two pointers: begin-end, one point to tail and one  head
int begin = 0, end = 0;
//distance between begin and end
int min = Integer.MAX_VALUE;
//head pointer of the result substring

//loop through s
while(end < s.length()){
//get a character
char c = s.charAt(end);
//if the map contains the character c, we consider it as a effective character
if(map.containsKey(c)){
//then increment the count by 1
map.put(c, map.get(c)-1);
//because the character c exists in t, we have to consider it as a valid character
if(map.get(c) >= 0)
//increment the count by 1
count ++;
}
end++;

//when the count is equal to t's length, in other word, find a valid substring
while(count == t.length()){
//if find a substring whose length is less than min, then update min
if(end-begin < min)

//if the map contains the character s[begin], we should plus one to make it invalid/not effective again
char tempc = s.charAt(begin);
if(map.containsKey(tempc)){
map.put(tempc, map.get(tempc) + 1);
//plus one make it invalid
if(map.get(tempc) > 0)
//decrement the count by 1
count--;
}
//move the begin pointer to find the new substring
begin ++ ;
}

}
//return the result substring
if(min == Integer.MAX_VALUE)
return "";
}
}```
```Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.```
```/**
* @param {string} s
* @param {string} t
* @return {string}
*/

// this is a sliding window problem

var minWindow = function(s, t) {
let map = {};
let count = t.length;
let min = Infinity;
let minStart = 0;

// fill up the map with the counts of each character in t
for (let i = 0; i < t.length; i++) {
let c = t.charAt(i);
map[c] = map[c] + 1 || 1;
}

// two pointers, left and right
// as we move right, we decrement the count for each character we see in t
// as soon as the count is 0, we know we have found all the characters in t
// we then move left until the count is no longer 0
// we keep track of the minimum length window
let left = 0;
for (let right = 0; right < s.length; right++) {
let c = s.charAt(right);

if (map[c] > 0) {
count--;
}

map[c]--;

while (count === 0) {
if (right - left + 1 < min) {
min = right - left + 1;
minStart = left;
}

let d = s.charAt(left);
map[d]++;

if (map[d] > 0) {
count++;
}

left++;
}
}

return min === Infinity ? "" : s.substring(minStart, minStart + min);
};```
```class Solution {
public:
string minWindow(string s, string t) {
// Base case
if (t.size() > s.size()) return "";

// Initialize a map to keep track of all the unique characters in t
unordered_map target;
for (char c : t) target[c]++;

// Initialize a map to keep track of the unique characters we've seen so far
unordered_map seen;

// Initialize two pointers, left and right
int left = 0, right = 0;

// Initialize a variable to keep track of the number of unique characters we've seen so far
int unique = 0;

// Initialize a variable to keep track of the length of the smallest window
int minLen = INT_MAX;

// Initialize a variable to keep track of the starting index of the smallest window
int start = 0;

// Loop through the string
while (right < s.size()) {
// If the character at the current index is not in the map, skip it
if (target.find(s[right]) == target.end()) {
right++;
continue;
}

// If the character at the current index is in the map, increment the value at that key
seen[s[right]]++;

// If the character at the current index is in the map and we haven't seen it before, increment the unique counter
if (seen[s[right]] == target[s[right]]) unique++;

// If we've seen all the unique characters, move the left pointer
while (unique == target.size()) {
// If the current window is smaller than the smallest window we've seen so far, update the minimum length and starting index
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}

// If the character at the left pointer is not in the map, move the left pointer and continue
if (target.find(s[left]) == target.end()) {
left++;
continue;
}

// If the character at the left pointer is in the map, decrement the value at that key
seen[s[left]]--;

// If the character at the left pointer is in the map and we've seen it before, decrement the unique counter
if (seen[s[left]] < target[s[left]]) unique--;

// Move the left pointer
left++;
}

// Move the right pointer
right++;
}

// Return the smallest window
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}
};```
```public class Solution {
public string MinWindow(string s, string t) {
// edge case: s is shorter than t
if (s.Length < t.Length) {
return "";
}

// initialize a hashmap to store the characters in t and their counts
var map = new Dictionary();
foreach (char c in t) {
if (!map.ContainsKey(c)) {
map[c] = 0;
}
map[c]++;
}

// initialize variables to keep track of the minimum window
int minWindowStart = 0;
int minWindowEnd = 0;
int minWindowLength = int.MaxValue;

// initialize variables to keep track of the number of unique characters and the number of characters that have been matched so far
int uniqueChars = map.Count;
int matchedChars = 0;

// initialize two pointers, left and right, to keep track of the current window
int left = 0;
int right = 0;

// while the right pointer is less than the length of the string
while (right < s.Length) {
// if the character at the right pointer is in the hashmap
if (map.ContainsKey(s[right])) {
// decrement the count for that character
map[s[right]]--;
// if the count is now 0 (meaning we've matched all occurrences of that character), increment the matched characters counter
if (map[s[right]] == 0) {
matchedChars++;
}
}
// increment the right pointer
right++;

// while the unique characters counter is equal to the matched characters counter (meaning we've found a window that contains all the characters in t)
while (uniqueChars == matchedChars) {
// if the current window is smaller than the minimum window, update the minimum window
if (right - left < minWindowLength) {
minWindowLength = right - left;
minWindowStart = left;
minWindowEnd = right;
}

// if the character at the left pointer is in the hashmap
if (map.ContainsKey(s[left])) {
// increment the count for that character
map[s[left]]++;
// if the count is now greater than 0 (meaning we've unmatched one occurrence of that character), decrement the matched characters counter
if (map[s[left]] > 0) {
matchedChars--;
}
}
// increment the left pointer
left++;
}
}

// return the minimum window
return minWindowLength == int.MaxValue ? "" : s.Substring(minWindowStart, minWindowEnd - minWindowStart);
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]