easy 9ms C++ solution with explanation

  • 0
    class Solution {
        int lengthOfLongestSubstringKDistinct(string s, int k) {
            if (!k || s.empty()) return 0;
            int last_appear[256];
            for (int i=0; i<256; i++){
                last_appear[i] = -1;
            int count = 0; // record how many distinct elements are in the window [i,j]
            int i=0, j=0;
            int longest = 0;
            while (j<s.size()){
                // judge current window [i, j]
                // move j to next, if count<k || (s[j] is in the window)
                if (count<k || i<=last_appear[s[j]]){
                    longest = max(longest, j-i+1);
                    // new element in the window
                    if (last_appear[s[j]]<i) count++;
                    last_appear[s[j]] = j;
                // move i to next, if s[i] is a last one, count--
                    if (last_appear[s[i]]==i) count--;
            return longest;

Log in to reply

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