lintcode 928. 最多有两个不同字符的最长子串 尺取法

缘起

日常浪费生命~ lintcode 928. 最多有两个不同字符的最长子串

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个字符串，找出最长子串T的长度，它最多包含2种不同的字符。

样例
Example 1
Input: “eceba”
Output: 3

Explanation:
T is "ece" which its length is 3.

Example 2
Input: “aaa”
Output: 3

其实就是【1】的简单推广而已，直接copy代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    /**
     * @param s: A string
     * @return: An integer
     */
    int lengthOfLongestSubstringTwoDistinct(string &s) {
    	int k = 2; // 就是把【1】中的k换成2就行了
		memset(cnt,0,sizeof(cnt));
		int ans = 0, len = s.length(), num = 0; // num是字符的种类数量
		for (int i = 0,j = 0;i<len; i++)
		{
			if (!cnt[s[i]-'A']++) // 如果是新的种类的字符出现, 尺取虫的头部进动
			{
				++num;
			}
			if (num<=k) // 满足条件就更新
			{
				ans = max(ans, i-j+1);
			}
			while(num>k) // 如果不满足了, 尺取虫的尾部就进动直至满足, 不需要更新答案,肯定没有之前来的大
			{
				if (!--cnt[s[j++]-'A'])
				{
					--num;
				}
			}
		}
		return ans;
    }

	int cnt[100]; // 表示各种字符的出现数量
};

ac情况

1
2
3
4
5
Accepted
由 LintCode领扣极速闪测 强力驱动
100%
100% 数据通过测试总耗时 139 ms
您的提交打败了 73.91% 的提交!

参考

【1】https://yfsyfs.github.io/2019/10/11/lintcode-386-%E6%9C%80%E5%A4%9A%E6%9C%89k%E4%B8%AA%E4%B8%8D%E5%90%8C%E5%AD%97%E7%AC%A6%E7%9A%84%E6%9C%80%E9%95%BF%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2-%E5%B0%BA%E5%8F%96%E6%B3%95/