// 判断左侧窗口是否要收缩 for left < right && window needs shrink { //replace "window needs shrink" with actual condition // d 是将移出窗口的字符 d := rune(s[left]) window[d]-- // 缩小窗口 left++ // 进行窗口内数据的一系列更新 ... } } }
class Solution { public String minWindow(String s, String t) { Map<Character, Integer> need = new HashMap<>(); Map<Character, Integer> window = new HashMap<>(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); }
int left = 0, right = 0; int valid = 0; // 记录最小覆盖子串的起始索引及长度 int start = 0, len = Integer.MAX_VALUE; while (right < s.length()) { // c 是将移入窗口的字符 char c = s.charAt(right); // 扩大窗口 right++; // 进行窗口内数据的一系列更新 if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if (window.get(c).equals(need.get(c))) valid++; }
// 判断左侧窗口是否要收缩 while (valid == need.size()) { // 在这里更新最小覆盖子串 if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 char d = s.charAt(left); // 缩小窗口 left++; // 进行窗口内数据的一系列更新 if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) valid--; window.put(d, window.get(d) - 1); } } } // 返回最小覆盖子串 return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); } }
class Solution { public: string minWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) { need[c]++; }
int left = 0, right = 0; // 记录window中的字符满足need条件的字符个数 int valid = 0; // 记录最小覆盖子串的起始索引及长度 int start = 0, len = INT_MAX; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 扩大窗口 right++; // 进行窗口内数据的一系列更新 if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; }
// 判断左侧窗口是否要收缩 while (valid == need.size()) { // 在这里更新最小覆盖子串 if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 char d = s[left]; // 缩小窗口 left++; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } // 返回最小覆盖子串 return len == INT_MAX ? "" : s.substr(start, len); } };
class Solution: def minWindow(self, s: str, t: str) -> str: need, window = {}, {} for c in t: need[c] = need.get(c, 0) + 1
left = 0 right = 0 valid = 0 # 记录最小覆盖子串的起始索引及长度 start = 0 length = float('inf') while right < len(s): # c 是将移入窗口的字符 c = s[right] # 扩大窗口 right += 1 # 进行窗口内数据的一系列更新 if c in need: window[c] = window.get(c, 0) + 1 if window[c] == need[c]: valid += 1
# 判断左侧窗口是否要收缩 while valid == len(need): # 在这里更新最小覆盖子串 if right - left < length: start = left length = right - left # d 是将移出窗口的字符 d = s[left] # 缩小窗口 left += 1 # 进行窗口内数据的一系列更新 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1
func minWindow(s string, t string) string { need, window := make(map[byte]int), make(map[byte]int) for i := range t { need[t[i]]++ }
left, right := 0, 0 valid := 0 // 记录最小覆盖子串的起始索引及长度 start, length := 0, math.MaxInt32 for right < len(s) { // c 是将移入窗口的字符 c := s[right] // 扩大窗口 right++ // 进行窗口内数据的一系列更新 if _, ok := need[c]; ok { window[c]++ if window[c] == need[c] { valid++ } }
// 判断左侧窗口是否要收缩 for valid == len(need) { // 在这里更新最小覆盖子串 if right - left < length { start = left length = right - left } // d 是将移出窗口的字符 d := s[left] // 缩小窗口 left++ // 进行窗口内数据的一系列更新 if _, ok := need[d]; ok { if window[d] == need[d] { valid-- } window[d]-- } } } // 返回最小覆盖子串 if length == math.MaxInt32 { return "" } return s[start : start+length] }
var minWindow = function(s, t) { let need = {}, window = {}; for (let c of t) { need[c] = (need[c] || 0) + 1; }
let left = 0, right = 0; let valid = 0; // 记录最小覆盖子串的起始索引及长度 let start = 0, len = Infinity; while (right < s.length) { // c 是将移入窗口的字符 let c = s[right]; // 扩大窗口 right++; // 进行窗口内数据的一系列更新 if (need[c]) { window[c] = (window[c] || 0) + 1; if (window[c] === need[c]) { valid++; } }
// 判断左侧窗口是否要收缩 while (valid === Object.keys(need).length) { // 在这里更新最小覆盖子串 if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 let d = s[left]; // 缩小窗口 left++; // 进行窗口内数据的一系列更新 if (need[d]) { if (window[d] === need[d]) { valid--; } window[d]--; } } } // 返回最小覆盖子串 return len === Infinity ? "" : s.substring(start, start + len); };
class Solution { // 判断 s 中是否存在 t 的排列 public boolean checkInclusion(String t, String s) { Map<Character, Integer> need = new HashMap<>(); Map<Character, Integer> window = new HashMap<>(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); }
int left = 0, right = 0; int valid = 0; while (right < s.length()) { char c = s.charAt(right); right++; // 进行窗口内数据的一系列更新 if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if (window.get(c).intValue() == need.get(c).intValue()) valid++; }
// 判断左侧窗口是否要收缩 while (right - left >= t.length()) { // 在这里判断是否找到了合法的子串 if (valid == need.size()) return true; char d = s.charAt(left); left++; // 进行窗口内数据的一系列更新 if (need.containsKey(d)) { if (window.get(d).intValue() == need.get(d).intValue()) valid--; window.put(d, window.get(d) - 1); } } } // 未找到符合条件的子串 return false; } }
class Solution { public: // 判断 s 中是否存在 t 的排列 bool checkInclusion(string t, string s) { unordered_map<char, int> need, window; for (char c : t) { need[c]++; }
int left = 0, right = 0; int valid = 0; while (right < s.size()) { char c = s[right]; right++; // 进行窗口内数据的一系列更新 if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; }
// 判断左侧窗口是否要收缩 while (right - left >= t.size()) { // 在这里判断是否找到了合法的子串 if (valid == need.size()) return true; char d = s[left]; left++; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } // 未找到符合条件的子串 return false; } };
class Solution: # 判断 s 中是否存在 t 的排列 def checkInclusion(self, t: str, s: str) -> bool: need, window = collections.defaultdict(int), collections.defaultdict(int) for c in t: need[c] += 1
left, right, valid = 0, 0, 0 while right < len(s): c = s[right] right += 1 # 进行窗口内数据的一系列更新 if c in need: window[c] += 1 if window[c] == need[c]: valid += 1
# 判断左侧窗口是否要收缩 while (right - left >= len(t)): # 在这里判断是否找到了合法的子串 if valid == len(need): return True d = s[left] left += 1 # 进行窗口内数据的一系列更新 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1
// 判断 s 中是否存在 t 的排列 func checkInclusion(t string, s string) bool { need := make(map[rune]int) window := make(map[rune]int)
for _, c := range t { need[c]++ }
left, right := 0, 0 valid := 0 for right < len(s) { c := rune(s[right]) right++ // 进行窗口内数据的一系列更新 if _, ok := need[c]; ok { window[c]++ if window[c] == need[c] { valid++ } }
// 判断左侧窗口是否要收缩 for right - left >= len(t) { // 在这里判断是否找到了合法的子串 if valid == len(need) { return true } d := rune(s[left]) left++ // 进行窗口内数据的一系列更新 if _, ok := need[d]; ok { if window[d] == need[d] { valid-- } window[d]-- } } }
var checkInclusion = function(t, s){ var need = new Map(); var window = new Map(); for (var c of t) { need.set(c, (need.get(c) || 0) + 1); }
var left = 0, right = 0; var valid = 0; while (right < s.length) { var c = s[right]; right++; // 进行窗口内数据的一系列更新 if (need.has(c)) { window.set(c, (window.get(c) || 0) + 1); if (window.get(c) === need.get(c)) valid++; }
// 判断左侧窗口是否要收缩 while (right - left >= t.length) { // 在这里判断是否找到了合法的子串 if (valid === need.size) return true; var d = s[left]; left++; // 进行窗口内数据的一系列更新 if (need.has(d)) { if (window.get(d) === need.get(d)) valid--; window.set(d, window.get(d) - 1); } } } // 未找到符合条件的子串 return false; };
对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变几个地方：
1、本题移动 left 缩小窗口的时机是窗口大小大于 t.length() 时，因为排列嘛，显然长度应该是一样的。
class Solution { public List<Integer> findAnagrams(String s, String t) { Map<Character, Integer> need = new HashMap<>(); Map<Character, Integer> window = new HashMap<>(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); }
int left = 0, right = 0; int valid = 0; // 记录结果 List<Integer> res = new ArrayList<>(); while (right < s.length()) { char c = s.charAt(right); right++; // 进行窗口内数据的一系列更新 if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if (window.get(c).equals(need.get(c))) { valid++; } } // 判断左侧窗口是否要收缩 while (right - left >= t.length()) { // 当窗口符合条件时，把起始索引加入 res if (valid == need.size()) res.add(left); char d = s.charAt(left); left++; // 进行窗口内数据的一系列更新 if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return res; } }
class Solution: def findAnagrams(self, s: str, t: str) -> List[int]: need = {} window = {} for c in t: need[c] = need.get(c, 0) + 1
left = 0 right = 0 valid = 0 # 记录结果 res = [] while right < len(s): c = s[right] right += 1 # 进行窗口内数据的一系列更新 if c in need: window[c] = window.get(c, 0) + 1 if window[c] == need[c]: valid += 1 # 判断左侧窗口是否要收缩 while right - left >= len(t): # 当窗口符合条件时，把起始索引加入 res if valid == len(need): res.append(left) d = s[left] left += 1 # 进行窗口内数据的一系列更新 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1
func findAnagrams(s string, t string) []int { need, window := make(map[rune]int), make(map[rune]int) for _, c := range t { need[c]++ }
left, right := 0, 0 valid := 0 // 记录结果 var res []int for right < len(s) { c := rune(s[right]) right++ // 进行窗口内数据的一系列更新 if _, ok := need[c]; ok { window[c]++ if window[c] == need[c] { valid++ } } // 判断左侧窗口是否要收缩 for right - left >= len(t) { // 当窗口符合条件时，把起始索引加入 res if valid == len(need) { res = append(res, left) } d := rune(s[left]) left++ // 进行窗口内数据的一系列更新 if _, ok := need[d]; ok { if window[d] == need[d] { valid-- } window[d]-- } } } return res }
var lengthOfLongestSubstring = function(s) { var window = {}; var left = 0, right = 0; // 记录结果 var res = 0; while (right < s.length) { var c = s.charAt(right); right++; // 进行窗口内数据的一系列更新 window[c] = (window[c] || 0) + 1; // 判断左侧窗口是否要收缩 while (window[c] > 1) { var d = s.charAt(left); left++; // 进行窗口内数据的一系列更新 window[d] = window[d] - 1; } // 在这里更新答案 res = Math.max(res, right - left); } return res; };
这就是变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。
当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。
唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？
这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。
