一、无重复字符的最长子串
题目描述
定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
题目链接：无重复字符的最长子串
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：运用滑动窗口记录当前窗口内已经出现的字符，窗口右边向右移动，如果遇到之前重复字符，则把窗口左边右移，直至重复字符挪出窗口。重复此操作直至窗口右边抵达字符串末尾。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//窗口内当前出现过的字符
std::unordered_set<char> curstr;
int maxlen = 0;
int left = 0, right = 0;
int len = s.size();
while (right < len)
{
//如果遇到了重复字符，就把窗口左边右移，直到重复字符被移出
while (curstr.find(s[right]) != curstr.end())
curstr.erase(s[left++]);
curstr.insert(s[right]);
maxlen = std::max(maxlen, right - left + 1);
++right;
}
return maxlen;
}
};
二、找到字符串中所有字母异位词
题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
题目链接：找到字符串中所有字母异位词
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
思路：定义一个滑动窗口，内部记录的是所有在窗口内出现过的字符，向右移动整个窗口，新进窗口的字符的出现次数+1，被移出窗口的字符的出现次数-1，如果窗口内的字符出现次数等于目标字符串的字符出现次数，则为一个解。重复此步骤，直至窗口右边达到终点。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int len = s.size();
int lookuplen = p.size();
if (lookuplen > len)
return {};
vector<int> scount(26);
vector<int> pcount(26);
for (int i = 0; i < lookuplen; ++i)
{
++scount[s[i] - 'a'];
++pcount[p[i] - 'a'];
}
vector<int> res;
if (scount == pcount)
res.emplace_back(0);
for (int i = 0; i < len - lookuplen; ++i)
{
++scount[s[i + lookuplen] - 'a'];
--scount[s[i] - 'a'];
if (scount == pcount)
res.emplace_back(i + 1);
}
return res;
}
};
三、串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
题目链接：串联所有单词的子串
例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
思路：由于words 中所有字符串 长度相同，我们把字符串s按照words中字符串的长度进行拆解，这样就可以把每一个字符串，看成是上一题中的一个字符，即可用类似上一题的解法。拆解字符串时，有从第0个位置开始一直到words中一个字符串长度减一种拆解方案。定义一个滑动窗口，内部记录的是所有在窗口内出现过的字符串，向右移动整个窗口，新进窗口的字符串的出现次数+1，被移出窗口的字符串的出现次数-1，如果窗口内的字符串出现次数等于目标字符串的字符串出现次数，则为一个解。重复此步骤，直至窗口右边达到终点。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int slen = s.size();
int wordslen = words.size();
int onewordlen = words[0].size();
if (slen < onewordlen * wordslen)
return {};
//滑动窗口内部的字符串出现的次数
std::unordered_map<std::string, int> lookupstrtimes;
//目标字符串出现的次数
std::unordered_map<std::string, int> targetstrtimes;
for (auto &str : words)
{
++targetstrtimes[str];
}
vector<int> res;
//从0到onewordlen长度进行拆解
for (int index = 0; index < onewordlen; ++index)
{
vector<string> curstr;
//
for (int i = index; i < slen; i += onewordlen)
{
if (i + onewordlen > slen)
break;
//进行拆解
curstr.push_back(s.substr(i, onewordlen));
}
int curlen = curstr.size();
if (curlen < wordslen)
continue;
lookupstrtimes.clear();
for (int i = 0; i < wordslen; ++i)
{
++lookupstrtimes[curstr[i]];
}
if (lookupstrtimes == targetstrtimes)
res.emplace_back(index);
for (int i = 0; i < curlen - wordslen; ++i)
{
++lookupstrtimes[curstr[i + wordslen]];
if (--lookupstrtimes[curstr[i]] == 0)
lookupstrtimes.erase(curstr[i]);//必须erase，哪怕是0，由于目标字符串的map中没有这个key会判断两个map不相等
if (lookupstrtimes == targetstrtimes)
res.emplace_back(index + (i + 1) * onewordlen);
}
}
return res;
}
};