lc340 - Longest Substring with At Most K Distinct Characters

發表於   |   分類於   |   0 comments   |  

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is “ece” which its length is 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int hash[128] = {0};
        int j = 0;
        int l = s.length();
        int cur_nchar=0, max_len=0;
        for (int i=0; i<l; i++) {
            if(!hash[s[i]]++) cur_nchar++;
            if (cur_nchar <= k) max_len = max(max_len, i-j+1);
            while(cur_nchar > k) {
                if (!--hash[s[j++]]) cur_nchar--;
            }
            
        }
        return max_len;
    }
};

Dec 8 update:
mistakes made: thought there are only letters but all ASCII characters are possible input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int end = 0;
        int start = 0;
        int len = s.length();
        int cnt = 0;
        vector<int> v(256, 0);
        int max = 0;
        while(end<len) {
            if (!(v[(256+int(s[end++]))%256]++)) cnt++;
            while (cnt > k) {
                // move start
                if (!--v[(256+int(s[start++]))%256]) cnt--;
            }
            if (end-start > max)
                max = end-start;
        }
        return max;
    }
};