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

缘起

继续浪费生命~ lintcode 386. 最多有k个不同字符的最长子字符串

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
描述
中文
English
给定字符串S，找到最多有k种不同字符的最长子串T。

您在真实的面试中是否遇到过这个题？  
样例
样例 1:

输入: S = "eceba" 并且 k = 3
输出: 4
解释: T = "eceb"
样例 2:

输入: S = "WORLD" 并且 k = 4
输出: 4
解释: T = "WORL" 或 "ORLD"
挑战
O(n) 时间复杂度

显然是尺取法. 

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
     * @param k: An integer
     * @return: An integer
     */
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
		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% 数据通过测试总耗时 50 ms
您的提交打败了 99.40% 的提交!