C++ 解法, 执行用时: 6ms, 内存消耗: 780KB, 提交时间: 2022-05-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int longestSubstring(string s, int k) {
        // write code here
        int arr[256]={0};
        int maxLength=0;
        int diff=0;//记录不同字符的种类
        int R=0;//其中R是窗口又边界
        for(int i=0;i<s.size();i++)
        {
            while(R<s.size()&&(diff<k||(diff==k&&arr[s[R]]>0)))
            {
                diff+=arr[s[R]]==0?1:0;
                arr[s[R++]]++;
            }
            //窗口第一次来到违规的位置
            maxLength=max(maxLength,R-i);
            diff-=arr[s[i]]==1?1:0;
            arr[s[i]]--;//出现次数减少
        }
        return maxLength;
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 784KB, 提交时间: 2022-07-03

class Solution {
  public:
    int longestSubstring(string s, int k) {
        int a[256] = {0};
        int h = 0, x = 0, j = 0;
        
        for (int i = 0; i < s.size(); i++) {
            while (j < s.size() && (x < k || (x == k && a[s[j]] > 0))) {
                x += a[s[j]] == 0 ? 1 : 0;
                a[s[j++]]++;
            }
            h = max(h, j - i);
            x -= a[s[i]] == 1 ? 1 : 0;
            a[s[i]]--;
        }
        return h;
    }
};

C 解法, 执行用时: 7ms, 内存消耗: 652KB, 提交时间: 2022-06-26

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param k int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int max(int a, int b) {
    return a > b ? a : b;
}

int longestSubstring(char* s, int k ) {
    int maxLen = 0, sLen = strlen(s), chCount = 0, chHash[26] = { 0 }, key;
    int i = 0, j = 0;
    while(j < sLen) {
        key = s[j] - 'a';
        if (chHash[key] == 0) {
            chHash[key] = 1;
            chCount++;
        } else {
            chHash[key] += 1;
        }
        if (chCount == k + 1) {
            maxLen = max(maxLen, j-i);
            
            while(i < j) {
                chHash[s[i]-'a'] -= 1;
                
                i++;
                
                if (chHash[s[i-1]-'a'] == 0) {
                    chCount--;
                    break;
                }
            }
        }
        
        j++;
    }
    if (chCount <= k) {
        maxLen = max(maxLen, j - i);
    }
    
    return maxLen;
}

C 解法, 执行用时: 7ms, 内存消耗: 684KB, 提交时间: 2022-07-18

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param k int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int longestSubstring(char* s, int k ) {
    // write code here
    if(!k)
        return 0;
    int length=strlen(s);
    int left=0,right=0;
    int maxlength=1;  //记录最长子串长度
    int count=0;  //记录窗口中不同字符的个数
    int hash[128]={0};  //用哈希表来记录窗口中各字符个数,0表示不在窗口，非零整数表示在窗口
    while(right<length){
        hash[s[right]]++;
        if(hash[s[right]]==1)   //哈希表里唯一的该字符  
            count++;
        while(count>k){ //如果窗口里不同字符数超过k,移动left指针    
            hash[s[left]]--;
            if(hash[s[left]]==0)
                count--;
            left++;
        }
        maxlength=fmax(maxlength,right-left+1);
        right++;
    }
    return maxlength;
}

C 解法, 执行用时: 7ms, 内存消耗: 684KB, 提交时间: 2022-07-03

int max(int a, int b) {return a > b ? a : b;}

int longestSubstring(char* s, int k ) {
    int a[256] = {0};
    int h = 0, x = 0, j = 0;
    for (int i = 0; i < strlen(s); i++) {
        while (j < strlen(s) && (x < k || (x == k && a[s[j]] > 0))) {
            x += a[s[j]] == 0 ? 1 : 0;
            a[s[j++]]++;
        }
        h = max(h, j - i);
        x -= a[s[i]] == 1 ? 1 : 0;
        a[s[i]]--;
    }
    return h;
}