Concise solution use sliding window and hash


  • 0
    M
    int lengthOfLongestSubstringKDistinct(string s, int k) {
            int hsh[270] = {0};
            int cur = 0, mx = 0, start = 0;
            for (int i = 0; i < s.length(); i++) {
                // keep a substring from start to i, s[start], s[start + 1], ... , s[i]
                hsh[s[i]]++;
                int cnt = count(hsh);
                while (cnt > k) {
                    hsh[s[start]]--;
                    ++start;
                    cnt = count(hsh);
                }     
                // use mx to save the maxmum value from s[start] to s[i], i - start + 1
                if (i - start + 1 > mx) mx = i - start + 1;
            }
            return mx;
        }
        
        int count(int hsh[]) {
            int cnt = 0;
            for (int i = 0; i < 270; i++) {
                if (hsh[i] > 0) cnt++;
            }
            return cnt;
        }
    

  • 0
    M

    short Java solution thanks to @jiangbowei2010 .

     public int lengthOfLongestSubstringKDistinct(String s, int k) {
            int[] ch = new int[256];
            int num = 0, start = 0, mx = 0;
            for (int i = 0; i < s.length(); i++) {
                if (ch[s.charAt(i)]++ == 0) num++;
                while (num > k) {
                    if (ch[s.charAt(start++)]-- == 1) num--;
                }
                mx = Math.max(i + 1 - start, mx);
            }
            return mx;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.