LeetCode 340 [Longest Substring

原题

给定一个字符串，找到最多有k个不同字符的最长子字符串。

样例
例如，给定 s = "eceba" , k = 3,
T 是 "eceb"，长度为 4.

解题思路

• 找子串 - 窗口问题
• 如果套用通常的if+while模板，里面需要考虑几种Corner Case
• len(s) < k - 可以直接返回s的长度
• 跳出循环是因为len(sourceHash) > k - 那其实一定就等于 k + 1，此时如果符合条件，则更新length
• 跳出循环是因为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