76.最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
参考
JAVA
class Solution {
public String minWindow(String s, String t) {
HashMap need = new HashMap<>();
HashMap window = new HashMap<>();
//初始化need
for(int i = 0; i < t.length(); i++){
//统计t中各字符的词频
need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
}
//初始化左右指针及need计数器
int left = 0, right = 0;
int valid = 0;
int start = 0, len = Integer.MAX_VALUE;
while(right < s.length()){
//右侧元素从右侧进入滑窗
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
if(need.get(c).equals(window.get(c))){
valid++;
}
}
//判断窗口左侧是否要收缩
while(valid == need.size()){
if(right - left < len){
start = left;
len = right - left;
}
//移出窗口
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(need.get(d).equals(window.get(d))) valid--;
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
C++
class Solution {
public:
string minWindow(string s, string t) {
//将t转为char存入map，方便比对
//need为目标字符串的char组，window为滑窗对应的char组
unordered_map need, window;
//初始化need
for(char c:t) need[c]++;
//初始化左右指针及need计数器
int left = 0, right = 0;
//window中满足need的字符个数记作valid
int valid = 0;
//s中选出的子串起始位置及长度
int start = 0, len = INT_MAX;
//当窗右边界在s长度内时
while(right < s.size()){
//右侧元素c 从右侧进入滑窗
char c = s[right];
right++;
//如果目标t字符串中包含c，则进一步判断
if(need.count(c)){
//滑窗window内c数量+1
window[c]++;
//如果滑窗window和need中，c的个数相等，则valid++
if(window[c] == need[c]){
valid++;
}
}
//判断窗口左侧是否要收缩
//满足need要求，则滑窗左侧收缩
while(valid == need.size()){
//判断是否比上一子串长度len更短
//若更短,则更新start和len
if(right - left < len){
start = left;
len = right - left;
}
//将滑窗左侧元素d移出窗口
char d = s[left];
left++;
//判断need(t)中是否包含元素d
if(need.count(d)){
//若包含，则有效值valid减一
if(need[d] == window[d]) valid--;
//并更新窗口内元素，d个数减一
window[d]--;
}
}
}
return len == INT_MAX ? "":s.substr(start,len);
}
};
567. 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap need = new HashMap<>();
HashMap window = new HashMap<>();
for(int i = 0; i < s1.length(); i++){
need.put(s1.charAt(i),need.getOrDefault(s1.charAt(i), 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while(right < s2.length()){
char c = s2.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
if(need.get(c).equals(window.get(c))){
valid++;
}
}
while(right - left >= s1.length()){
if(valid == need.size()){
return true;
}
char d = s2.charAt(left);
if(need.containsKey(d)){
if(need.get(d).equals(window.get(d))){
valid--;
}
window.put(d, window.get(d) - 1);
}
left++;
}
}
return false;
}
}
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
class Solution {
public List findAnagrams(String s, String p) {
List ans = new ArrayList<>();
HashMap need = new HashMap<>();
HashMap window = new HashMap<>();
for(int i = 0; i < p.length(); i++){
need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while(right < s.length()){
char c = s.charAt(right);
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
if(need.get(c).equals(window.get(c))){
valid++;
}
}
right++;
while(right - left >= p.length()){
if(valid == need.size()){
ans.add(left);
}
char d = s.charAt(left);
if(need.containsKey(d)){
if(need.get(d).equals(window.get(d))){
valid--;
}
window.put(d, window.get(d) - 1);
}
left++;
}
}
return ans;
}
}
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap window = new HashMap<>();
int len = 0;
int left = 0, right = 0;
while(right < s.length()){
char c = s.charAt(right);
right++;
window.put(c, window.getOrDefault(c, 0) + 1);
while(window.get(c) > 1){
char d = s.charAt(left);
window.put(d, window.get(d) - 1);
left++;
}
len = Math.max(len, right - left);
}
return len;
}
}
