至多包含K种字符的子串

# -*- coding: utf-8 -*-

import collections


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param k int整型
# @return int整型
#
class Solution1:
    """
    题目：
        https://www.nowcoder.com/practice/04c926ef687340c3842a72edb5c23ede?tpId=196&tqId=40446&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法1：
        双指针i, j，分别指向窗口的左右边界，是用哈希表count统计窗口内每个字符出现次数，当前窗口不同字符的数量diffCnt就是count的长度。
        当diffCnt小于等于k时，移动右边界，更新res；否则移动左边界。重复该步骤，直到遍历完字符串s。
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(k)
    """

    def longestSubstring(self, s, k):
        # write code here
        n = len(s)

        count = {}
        i, j, res = 0, 0, 0
        while j < n:
            diffCnt = len(count)
            if diffCnt <= k:
                if s[j] not in count:
                    count[s[j]] = 1
                    res = max(res,
                              j - i)  # k = 3, s = "abcdef", i = 0, j = 3，计算长度diffCnt为j - i
                else:
                    count[s[
                        j]] += 1  # # k = 3, s = "abccdef", i = 0, j = 3，计算长度diffCnt为j - i + 1
                    res = max(res, j - i + 1)
                j += 1
            else:
                count[s[i]] -= 1
                if count[s[i]] == 0:
                    count.pop(s[i])
                i += 1

        return res


class Solution:
    """
    参考：
        大神：fred-coder
    算法2：
        遍历字符串s:
            使用哈希表count统计每个字符串出现次数，不同字符的个数就是count的长度，start记录当前有效区间的左边界，右边界为i。
            当count的长度小于等于k时，我们更新res；否则，我们移动左边界start，使得[start, i]区间内的不同字符数量满足小于等于k
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(k)
    """

    def longestSubstring(self, s, k):
        # write code here
        count = collections.defaultdict(int)
        start, res = 0, 0
        for i, ch in enumerate(s):
            count[ch] += 1
            if len(count) <= k:
                res = max(res, i - start + 1)
            else:
                j = start
                while j < i - k + 1 and len(count) > k:
                    count[s[j]] -= 1
                    if count[s[j]] == 0:
                        count.pop(s[j])
                    j += 1
                start = j
        return res


if __name__ == "__main__":
    sol = Solution()

    # s, k = "abcck", 1

    # s, k = "abcck", 2

    s, k = "efsarcbynec", 5

    # s, k = "jmowfrxsjybl", 1

    res = sol.longestSubstring(s, k)

    print res