Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2,
T is "ece" which its length is 3.
Solution:
class Solution(object):
def lengthOfLongestSubstringKDistinct(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
if k < 1: return 0
ht = {}
i = 0
res = 0
for j, c in enumerate(s):
ht[c] = j
if len(ht) < k + 1: continue
res = res if res > j - i else j - i
i = min(ht.values())
del ht[s[i]]
i += 1
res = res if res > len(s) - i else len(s) - i
return res
int lengthOfLongestSubstringKDistinct(char* s, int k) {
int count[256] = {0};
int l = 0, res = 0, already = 0;
int r;
for (r = 0; s[r]; r++) {
if (count[s[r]]++ == 0) already++;
if (already < k + 1) continue;
res = res > r - l ? res : r - l;
while (--count[s[l++]] > 0);
already--;
}
return res > r - l ? res : r - l;
}
Summary:
- Python: 82ms, 95.84%
- C: 3ms, 16.87%
- It's not hard, at most two pass. O(N)





近期评论