【子串】【困难】最小覆盖子串

题目给定两个字符串 s 和 t长度分别是 m 和 n返回 s 中的 最短窗口 子串使得该子串包含 t 中的每一个字符包括重复字符。如果没有这样的子串返回空字符串 “”。测试用例保证答案唯一。示例 1输入s “ADOBECODEBANC”, t “ABC”输出“BANC”解释最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。示例 2输入s “a”, t “a”输出“a”解释整个字符串 s 是最小覆盖子串。示例 3:输入: s “a”, t “aa”输出: “”解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中因此没有符合条件的子字符串返回空字符串。提示m s.lengthn t.length1 m, n 10^5s 和 t 由英文字母组成进阶你能设计一个在 O(m n) 时间内解决此问题的算法吗方法一暴力枚举所有子串然后依次判断是否包含子串此时枚举的复杂度为 O(n²)判断需要O(n)总体复杂度O(n³)不可取。方法二滑动窗口classSolution{publicStringminWindow(Strings,Stringt){MapCharacter,IntegerneednewHashMap();for(charc:t.toCharArray()){need.put(c,need.getOrDefault(c,0)1);}MapCharacter,IntegerwindownewHashMap();intleft0;intcount0;intstart0;intminLenInteger.MAX_VALUE;for(intright0;rights.length();right){charcs.charAt(right);window.put(c,window.getOrDefault(c,0)1);if(need.containsKey(c)window.get(c)need.get(c)){count;}while(countt.length()){if(right-left1minLen){minLenright-left1;startleft;}charremoves.charAt(left);window.put(remove,window.get(remove)-1);if(need.containsKey(remove)window.get(remove)need.get(remove)){count--;}left;}}returnminLenInteger.MAX_VALUE?:s.substring(start,startminLen);}}