至多包含K种字符的子串

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param k int整型 
 * @return int整型
*/
func longestSubstring( s string ,  k int ) int {
    max:=0
    cnt:=map[byte]int{}
    for l,r:=0,0;r<len(s);r++{
        cnt[s[r]]++
        for len(cnt)>k{
            if cnt[s[l]]==1{
                delete(cnt,s[l])
            }else{
                cnt[s[l]]--
            }
            l++
        }
        if r-l+1>max{
            max=r-l+1
        }
    }
    return max
}

# python3
class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # write code here
        lastPos = {}
        l, res = 0, 0
        for r in range(len(s)):
            if s[r] in lastPos:
                lastPos[s[r]] = r
            else:
                if len(lastPos) < k:
                    lastPos[s[r]] = r
                else:
                    lastPos[s[r]] = r
                    while l < lastPos[s[l]]:
                        l += 1
                    lastPos.pop(s[l], None)
                    l += 1
            res = max(res, r - l + 1)
        return res

# -*- 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

import java.util.*;

public class Solution {
    public int longestSubstring (String s, int k) {
        if(k > s.length() || s == null || s.length() == 0){
            return 0;
        }
        int res = 0;
        int l = 0;
        int count = 0;
        int[] arr = new int[26];
        for(int r = 0; r < s.length(); r++){
            char c = s.charAt(r);
            if(arr[c - 'a'] == 0){
                count++;
            }
            arr[c - 'a']++;
            while(count > k){
                if(arr[s.charAt(l) - 'a'] == 1){
                    count--;
                }
                arr[s.charAt(l) - 'a']--;
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}