• ㊗️
• 大家
• offer
• 多多！

## Problem

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.

A substring is a contiguous sequence of characters within the string.

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.


## Code

class Solution {
public String minWindow(String s, String t) {
int[] cnt = new int[128];
for(char c : t.toCharArray()){
cnt[c]++;
}

// 记录最小长度的起始位置
int from = 0;
// 判断是否找到t中的全部结果了
int total = t.length();
// 最小长度
int min = Integer.MAX_VALUE;
for(int i = 0, j = 0; i < s.length(); i++){
// 如果发现了t中的字符，就让total--
if(cnt[s.charAt(i)]-- > 0) total--;

// 先找到一个包含全部字符的
// 在当前的范围内找到了多有的字符
while(total == 0){
// 先判断最小长度
if(i - j + 1 < min){
min = i - j + 1;
from = j;
}

// 开始从左缩小窗口
// 如果s中的字符碰到了t中字符，并且此时对应的字符在cnt中为0
// 那么说明当前j指向的位置将会少一个t中的字符
// 此时total++，退出while循环，开始找下一个字符
if(cnt[s.charAt(j++)]++ == 0) total++;
}
}

return (min == Integer.MAX_VALUE) ? "" : s.substring(from, from + min);
}
}