C# solution beats 100% with O(n) amortized complexity


  • 0
    B
    public class Solution {
        public int LengthOfLongestSubstringKDistinct(string s, int k) {
            if(k == 0) return 0;    
            int[] distinctChars = new int[128];
            int start = 0, maxLen = 0, count = 0;
            for (int i = 0; i < s.Length; i++)
            {
                var ele = s[i];
                if (distinctChars[ele] == 0 && count == k)
                {
                    while (count > k - 1 && start < i)
                    {
                        var sEle = s[start];
                        distinctChars[sEle]--;
                        if (distinctChars[sEle] == 0) count--;
                        start++;
                    }
                }
                if(distinctChars[ele] == 0) count++;
                distinctChars[ele]++;
                if (i - start + 1 > maxLen)
                {
                    maxLen = i - start + 1;
                }
            }
            return maxLen;
        }
    }
    

Log in to reply
 

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