76. 最小覆盖子串

滑动窗口

思路和算法

我们在s上滑动窗口，通过移动right指针不断扩张窗口。当窗口包含t全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
在滑动窗口类型的问题中都会有两个指针，一个用于延伸现有窗口的right指针，和一个用于收缩窗口的left指针。在任意时刻，只有一个指针运动，而另一个保持静止。

如何判断当前的窗口包含所有t所需的字符呢？
首先，s和t中都可能出现重复的字符，所以我们要使用容器记录字符的个数。
哈希表needDict：保存所需字符的数量，即t中所有的字符以及它们的个数。
哈希表windowDict：保存当前滑窗[left,right]中存在的需要的字符的数量，所以在改变left和right的同时需要同步维护区间内字符的数量。
区间[left,right] 滑动窗口，左闭右开，经历过程：扩大---更新---覆盖---缩小---更新。窗口中包含t的字符，left右移，否则right右移。
区间[start,end] 暂存当前找到的最小覆盖子串，即最小间距的[left,right]，遍历完后就是最小覆盖子串的区间范围。
minLen 记录当前找到的最小覆盖子串的长度。
matchCnt 当前滑动窗口中匹配的个数

复杂度分析

• 时间复杂度：最坏情况下左右指针对s的每个元素各遍历一遍，哈希表中对s中的每个元素各插入、删除一次，对t中的元素各插入一次。每次检查是否可行会遍历整个t的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为C，则渐进时间复杂度为O(C⋅∣s∣+∣t∣)。
• 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为C ，则渐进空间复杂度为O(C)。