原題
給定一個字符串晌端，找到最多有k個不同字符的最長子字符串。
樣例
例如，給定 s = "eceba" , k = 3,
T 是 "eceb"，長度為 4.
解題思路
- 找子串 - 窗口問題
- 如果套用通常的if+while模板叔扼，里面需要考慮幾種Corner Case
- len(s) < k - 可以直接返回s的長度
- 跳出循環(huán)是因為len(sourceHash) > k - 那其實一定就等于 k + 1事哭，此時如果符合條件，則更新length
- 跳出循環(huán)是因為right = len(s) - 舉例"abababbaba" k = 3的情況瓜富，此時如果符合條件鳍咱，更新length
完整代碼
class Solution:
# @param s : A string
# @return : An integer
def lengthOfLongestSubstringKDistinct(self, s, k):
# write your code here
if not s or not k:
return 0
if len(s) < k:
return len(s)
right, length = 0, 0
sourceHash = {}
for left in range(len(s)):
while len(sourceHash) <= k and right < len(s):
if s[right] not in sourceHash:
sourceHash[s[right]] = 1
else:
sourceHash[s[right]] += 1
right += 1
if len(sourceHash) == k + 1 and right - left - 1 > length:
length = right - left - 1
elif right >= len(s) and right - left > length:
length = right - left
sourceHash[s[left]] -= 1
if sourceHash[s[left]] == 0:
del sourceHash[s[left]]
return length
