## Question

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.

**Follow up:** Could you find an algorithm that runs in `O(m + n)`

time?

## Approach

- Create a count array to store the count info( order does't matter)
- Left and right pointers move forward, if all the chars are included and the Len of substring is smaller, store the left and right info;
- Then move left pointer forward to keep looking for other combinations until s is traversed.

## Code1

- Right direction but don't pass, have some logic issues.
- Actually you don't need to use the includeAll to check the all the chars, use a integer len to keep the length record (if the t has been covered)

class Solution { public String minWindow(String s, String t) { if (t.length() > s.length()) { return ""; } Map<Character, Integer> map = new HashMap<>(); for (Character ch : t.toCharArray()) { if (!map.containsKey(ch)) { map.put(ch, 1); } else { map.put(ch, map.get(ch) + 1); } } String res = s; int left = 0, right = 0; while (right < s.length()) { char r_ch = s.charAt(right); char l_ch = s.charAt(left); if (map.get(r_ch) > 0) { map.put(r_ch, map.get(r_ch) - 1); } if (includeAll(map) && right - left + 1 < s.length()) { res = s.substring(left, right + 1); if (map.containsKey(l_ch)) map.put(l_ch, map.get(l_ch) + 1); left++; } else { right++; } } return res; } private boolean includeAll(Map<Character, Integer> map) { for (int i : map.keySet()) { if ((Integer) map.get(i) != 0) { return false; } } return true; } }

## Code2

class Solution { public String minWindow(String s, String t) { int[] count = new int[256]; for (char ch : t.toCharArray()) { count[ch]++; } int left = 0, right = 0; int len = t.length(); int min = Integer.MAX_VALUE; int from = 0; while (right < s.length()) { if (count[s.charAt(right)]-- > 0) { len--; } while (len == 0) { if (min > right - left + 1) { min = right - left + 1; from = left; } count[s.charAt(left)]++; if (count[s.charAt(left++)] > 0) { len++; } } right++; } return min == Integer.MAX_VALUE ? "" : s.substring(from, from + min); } }