leetcode 76. 最小笼罩子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
留神：
对于 t 中反复字符，咱们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，咱们保障它是惟一的答案。示例 1：
输出：s = "ADOBECODEBANC", t = "ABC"
输入："BANC"
应用两个哈希表，ht存字符串t的字符呈现次数。而后遍历字符串s，当某个字符次数还未到t中的次数，则示意该字符是无效字符[可用于笼罩t]。
双指针算加须要指针具备枯燥性，这样工夫复杂度能力为O(n)。
枯燥性证实：假如[j, i]之间的字符为涵盖t的一段，则当i往后走到i'，[j, i']必定也涵盖了t。此时j也只能往后走，因为要求的是最小子串。
什么时候j能够往后走：当s[j]呈现次数大于t中的次数时，阐明即便没有s[j]，[j, i]中也至多有了ht[s[j]]个s[j]了，故此时曾经不须要j地位字符。
unordered_map<char, int> hs, ht;string minWindow(string s, string t) { for (char c : t) ht[c]++; string ans; for (int i = 0, j = 0, cnt = 0; i < s.size(); i++) { hs[s[i]]++; if (hs[s[i]] <= ht[s[i]]) cnt++; while (hs[s[j]] > ht[s[j]]) // 不能是>=，因为只有当该字符在hs中冗余了，能力将该字符略过 hs[s[j++]]--; if (cnt == t.size()) { if (ans.empty() || i - j + 1 < ans.size()) ans = s.substr(j, i - j + 1); } } return ans;}leetcode 3. 无反复字符的最长子串
给定一个字符串 s ，请你找出其中不含有反复字符的 最长子串 的长度。
示例 1:
输出: s = "abcabcbb"
输入: 3
解释: 因为无反复字符的最长子串是 "abc"，所以其长度为 3。
指针枯燥性证实[反证]：假如[j, i]为以后无反复字符最长子串，则当i向后走到i'时，如果此时j往前走，[j', i]必定蕴含反复字符，不符题意。故当i往后，j也只能往后走。
什么时候j能够往后走：当新加进来的i字符反复了，此时就须要让j往后走，直到[j, i]无反复字符。
int lengthOfLongestSubstring(string s) { unordered_map<char, int> hmap; int ans = 0; for (int i = 0, j = 0; i < s.size(); i++) { hmap[s[i]]++; while (hmap[s[i]] > 1) hmap[s[j++]]--; ans = max(ans, i - j + 1); } return ans;}