3. 无重复的最长字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lengthOfLongestSubstring(string s) {
    int res = 0;
    //右指针
    int rp = -1;
    unordered_set<char> seri;
    //i是左指针
    for (int i = 0; i < s.size(); i++)
    {
        //每次循环开始的时候把上一次左指针指向的值删掉
        if (i != 0)
        {
            seri.erase(s[i - 1]);
        }
        //例如abcdcefgh，到了第二个c会产生重复，rp会停在d这里，然后删掉a继续循环，发现仍不满足!seri.count(s[rp + 1])，因为c并没被删掉，所以跳过while继续循环，删掉b，知道删掉第一个c，while中才满足!seri.count(s[rp + 1])，这时才能进入while，rp继续向后走
        while (rp + 1 < s.size() && !seri.count(s[rp + 1]))
        {
            seri.insert(s[rp + 1]);
            rp++;
        }
        res = max(res, rp - i + 1);
    }
    return res;
}

76. 最小覆盖字串

用两个map分别记录所需包含的字母及其个数(ori)，以及当前窗口内所含所需字母及其个数(cnt)

每次检查时，检查ori中的每个key对应的value和cnt中对应的value，cnt中的值不能小于ori，不然意味着当前窗口未完全包含所需的所有字符

1
2
3
4
5
6
7
8
9
10
11
bool check(unordered_map<char, int>& ori, unordered_map<char, int>& cnt)
{
    for(const auto& p : ori)
    {
    	if(cnt[p.first] < p.second)
        {
        	return false;
        }
    }
    return true;
}

当check满足条件，检查是否需要更新最小窗口长度len和结果起始点ansL，并且由于check满足条件需要将窗口左侧边界右移一位，所以此时如果最左侧的字母为ori中的一员，cnt对应的key的value减一

1
2
3
4
5
6
7
8
9
10
11
12
13
while(check(ori, cnt) && l <= r)
{
	if(r - l < minLength)
	{
		minLength = r - l;
		ansL = l;
	}
    if(ori.find(s[l]) != ori.end())
    {
    	--cnt[s[l]];
    }
	l++;
}