美文网首页
LeetCode #395 Longest Substring

LeetCode #395 Longest Substring

作者: 刘煌旭 | 来源:发表于2021-04-17 00:02 被阅读0次
    Longest_Substring.png
    int longestSubstring(char * s, int k){
        int len = 0, n = strlen(s);
        if (k == 1) return n;
        int first[26], start[n], num[26];
        for (int i = 0; i < 26; i++) { 
            num[i] = 0;
            first[i] = -1;
        }
        for (int i = 0; i < n; i++) { start[i] = i; }
        
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (first[c] == -1) { first[c] = i; }
            num[c]++;
            if (num[c] >= k) {
                int j = i - 1, left = first[c], min[26];
                for (int ic = 0; ic < 26; ic++) { min[ic] = 0; }
                min[c] = 1;
                while (j >= left && num[s[j] - 'a'] >= k) {
                    min[s[j] - 'a']++;
                    if (start[j] != j) { 
                        j = start[j]; 
                    } else {
                        j--;
                    } 
                    if (j >= 0 && num[s[j] - 'a'] >= k && left > first[s[j] - 'a']) { left = first[s[j] - 'a']; }
                }
                if (j == left - 1) {
                    int tlen = i - j;
                    if (len < tlen) { len = tlen; }
                } else {
                    int mink = n;
                    for (int ic = 0; ic < 26; ic++) { if (min[ic] != 0 && min[ic] < mink) { mink = min[ic]; } }
                    if (mink < n && mink >= k) {
                        int tlen = i - j;
                        if (len < tlen) { len = tlen; }
                    }
                }
            }
        }
        return len;
    }
    

    相关文章

      网友评论

          本文标题:LeetCode #395 Longest Substring

          本文链接:https://www.haomeiwen.com/subject/lkjylltx.html