# 76. Minimum Window Substring (Hard)

https://leetcode.com/problems/minimum-window-substring/

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.

## Solutions

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

// used to keep the count of the unique characters in t.
Map<Character, Integer> tCountMap = new HashMap<>();

for (int i = 0; i < t.length(); i++) {
int count = tCountMap.getOrDefault(t.charAt(i), 0);
tCountMap.put(t.charAt(i), count + 1);
}

// Number of unique characters in t, which need to be present in the desired window.
int reqChar = tCountMap.size();

// formedChar is used to keep track of how many unique characters in t
// are present in the current window in its desired frequency.

// e.g. if t is "AABC" then the window must have two A's, one B and one C.
// Thus formedChar would be = 3 when all these conditions are met.
int formedChar = 0;

// Dictionary which keeps an account of all the unique characters in the current window.
Map<Character, Integer> windowCountMap = new HashMap<>();

// ans list of the form (window length, left, right)
int[] ans = {-1, 0, 0};

// Left and Right pointer
int lptr = 0;
int rptr = 0;

while (rptr < s.length()) {
// Add one character from the right to the window
char c = s.charAt(rptr);

int count = windowCountMap.getOrDefault(c, 0);
windowCountMap.put(c, count + 1);

// If the frequency of the current character in current window equals to the
// desired count in t, then increase the formedChar count by 1.
// Be careful, it's not >= but ==, only add once after meets the desired count.

if (tCountMap.containsKey(c) && windowCountMap.get(c).intValue() == tCountMap.get(c).intValue()) {
formedChar++;
}

// Try to shrink the candidate window until it becomes the minimum sub set.
// Prune the leftmost character if possible to minimize the length of candidate substring.
while (lptr <= rptr && formedChar == reqChar) {

// Update the smallest window if possible.
if (ans[0] == -1 || (rptr - lptr + 1) < ans[0]) {
ans[0] = rptr - lptr + 1;
ans[1] = lptr;
ans[2] = rptr;
}

c = s.charAt(lptr);

// Reduce the count of lptr character since it is no longer a part of the window.
windowCountMap.put(c, windowCountMap.get(c) - 1);

if (tCountMap.containsKey(c) && windowCountMap.get(c).intValue() < tCountMap.get(c).intValue()) {
formedChar--;
}

// Move the left pointer forward, this would help to look for a new window.
// The new window are expected to has a more compact substring.

// AAABC will be sorted out at first, then try to prune head chars if possible
lptr++;
}

// Keep expanding the window on the rptr side once we are done shrinking.
rptr++;
}

return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}
``````