至多包含K种字符的子串

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int longestSubstring(string s, int k) {
        // write code here
        int l = 0 ,  r = 0 , res = 0 , sum = 0;//sum记录字符种类
        unordered_map<char , int> cnt;
        while(r < s.size())
        {
            if(!cnt[s[r]]) sum++;
            cnt[s[r]]++;
            while(sum > k)
            {
                cnt[s[l]]--;
                if(cnt[s[l]] == 0) sum--;
                l++;
            }
            res = max(res , r - l + 1);
            r++;
        }
        return res;
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param k int整型
# @return int整型
#
class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # write code here
        left = 0
        right = 0
        mp = dict()
        res = 0
        while right < len(s):
            if s[right] in mp:
                mp[s[right]] += 1
            else:
                mp[s[right]] = 1
            if len(mp) > k:
                mp.pop(s[left])
                left += 1
            res = max(res, right - left + 1)
            right += 1
        print(res)
        return res

class Solution:
    def longestSubstring(self , s: str, k: int) -> int:
        char_map = defaultdict(int)
        start = 0
        end = 0
        maxlen = 0
        while end < len(s):
            char_map[s[end]] += 1
            if len(char_map) > k:
                while len(char_map) > k:
                    char_map[s[start]] -= 1
                    if char_map[s[start]] == 0:
                        del char_map[s[start]]
                    start += 1
            end += 1
            maxlen = max(maxlen, end - start)
        return maxlen

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param k int整型 
# @return int整型
#
# 问题一：如何判断子串包含多少种不同字符
# hash，hash对应value不为0的key的个数
# k为限定条件，即不能使对应的value不为9的key的个数超过k，若超过，则移动左界
class Solution:
    def longestSubstring(self , s: str, k: int) -> int:
        # write code here
        if len(s) <= 1:
            return len(s)
        # 定义空字典
        dict_ = {}
        # 初始化左右界
        left = right = 0
        res = 0
        key_count = 0
        # 进入循环
        while right < len(s):
            # 将当前right的字符加入或者更新其在dict_中的value
            # 需要判断当前字符是否在字典之中
            if s[right] not in dict_:
                # 初始化key
                key_count += 1
                dict_[s[right]] = 1
            else:
                if dict_[s[right]] == 0:
                    key_count += 1
                # 更新对应key的value
                dict_[s[right]] += 1
            # 如果value >= 1的key的个数超过了k，则需要移动左界并更新字典，直到满足条件
            if key_count > k:
                while True:
                    # 把左界上面的字符的value清为0，就维持了条件
                    # 具体操作：更新value，移动左界
                    dict_[s[left]] -= 1
                    # 如果-1之后，左界指向的字符在字典里面value等于0了，移动左界并且跳出循环
                    if dict_[s[left]] == 0:
                        left += 1
                        break
                    # 不满足上面的条件，移动左界，进行循环
                    left += 1
                # 清零之后，更新一下key_count
                key_count -= 1
            # 经过上面的判断，此时必然满足条件，则计算子串长度，并与上一个res比较，如果更大，则更新res
            temp_res = right - left + 1
            if temp_res > res:
                res = temp_res
            # 在最后，移动右界
            right += 1

        return res

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;
    }
}