对于大多数子字符串问题，我们获得一个字符串和需要寻找一个符合条件的子字符串。一个通常的解法是使用hashmap来关联两个指针，接下来是模板：
思路：
使用count作为匹配数
对于单个字符串匹配问题，直接用一个窗口滑动，右窗滑动并更改count值，使count值符合完全匹配条件；左窗滑动令count值不符合完全匹配条件，从而重新迭代程序，使窗口向右滑动。
同理，对于两个字符串匹配问题，先把p串初始化到map里，然后用该map匹配s串。每次匹配成功则使count减一，直到count=0则完全匹配成功。
不过这模板也不一定都适合，比如最后的word串联匹配就相似，但还是右差别，要学会灵活应用。
int findSubstring(string s){ vector<int> map(128,0); int counter; // 检查子字符串是否符合 int begin=0, end=0; //two pointers, one point to tail and one head int d; //子字符串的长度 for() { /* 初始化hash map */ } while(end<s.size()){ if(map[s[end++]]-- ?){ /* 改变counter */ } while(/* counter condition */){ /* 如果是找最小串则在这里更新 d*/ //increase begin to make it invalid/valid again if(map[s[begin++]]++ ?){ /*改变counter */ } } /* 如果是找最大串则在这里更新 d*/ } return d; }
3. Longest Substring Without Repeating Characters
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
class Solution { public: int lengthOfLongestSubstring(string s) { vector<int> map(128,0); int counter=0, begin=0, end=0, d=0; while(end<s.size()){ if(map[s[end++]]++>0) counter++; //counter加一代表含有重复字母，右窗移动 while(counter>0) if(map[s[begin++]]-->1) counter--; //当存在重复字母时，左窗吐出一个值 d=max(d, end-begin); //while valid, update d } return d; } };
159.Longest Substring with At Most Two Distinct Characters
给出eceba，则输出ece的长度3
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s )
{
map<char,int> map;
int counter = 0, begin = 0, end = 0;
int len = 0;
while (end < s.size())
{
if (++map[s[end++]] == 1) counter++;
while (counter>2)//含有2种字符以上则窗口左边吐出一个
{
if (--map[s[begin]] == 0) counter--;
begin++;
}
len = max(len,end-begin);
}
return len;
}
};
76. Minimum Window Substring
string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto c: t) map[c]++;//初始化map
int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
while(end<s.size()){
if(map[s[end++]]-->0) counter--; //在s中遇到匹配的字符集则counter减一，
while(counter==0){ //窗口符合条件
if(end-begin<d) d=end-(head=begin);//更新最小长度d
if(map[s[begin++]]++==0) counter++; //若为匹配的字符则令counter加一；窗口左边吐出一个值 //若不匹配则窗口只单纯吐出一个值
}
}
return d==INT_MAX? "":s.substr(head, d);
}
438. Find All Anagrams in a String
给出字符串s和字符串t，在s中找出包含t字母随意排序的子字符串
class Solution { public: vector<int> findAnagrams(string s, string t ) { vector<int> res; if (t.size() > s.size()) return res; map<char, int> map; for (char c:t) map[c]++; int counter = map.size(), begin = 0, end = 0, head = 0; int len = INT_MAX; while (end < s.size()) { if (--map[s[end++]] == 0) counter--; while (counter==0) //当匹配的字符全部耗掉，即匹配成功，此时左窗吐值（吐t中的值时才匹配加一） { if (++map[s[begin]] > 0) counter++; if (end - begin == t.size()) res.push_back(begin); begin++;
}
} return res; } };
30、Substring with Concatenation of All Words
s="barfoothefoobarman"
words=["foo","bar"]
output:[0,9]
class Solution { public: vector<int> findSubstring(string S, vector<string> L) { vector<int> res; if (L.size() == 0 || S.size() < L.size() * L[0].size()) return res; int N = S.size(); int M = L.size(); int wl = L[0].size(); map<string, int> map,curMap; for (string s : L) map[s]++; string str, tmp; for (int i=0;i<wl;i++) { int count = 0; int start = i; for (int r=i;r+wl<=N;r+=wl)//每次前进一个word { str = S.substr(r,wl); if (map.find(str) != map.end()) //如果匹配的话，则curMap对应串加一 { curMap[str]++; if (curMap[str] <= map[str]) count++; //如果没全部匹配完，则匹配数加一 while (curMap[str]>map[str]) //前面是通过判断是否在map中存在当前字串就使curMap加一，会出现curMap的当前字串比实际要的（map）的要多
//此时要把多余的curMap字串去掉 { tmp = S.substr(start,wl); curMap[tmp]--; start += wl; if (curMap[tmp] < map[tmp]) count--; //如果去掉过头了，就把匹配的word数减一 } if (count==M) { res.push_back(start); tmp = S.substr(start,wl); curMap[tmp]--; //左窗吐出一个word start += wl; count--; //匹配的word数减一 } } else//如果窗口中没找到str，则清空当前窗口curMap和匹配数，并移位到下一个word { curMap.clear(); count = 0; start = r + wl; } } curMap.clear();//遍历完一次则清空curMap，以便进行下一次的遍历； } return res; } };