C# - simple O(n), coded for k characters


  • 0
    A

    The dictionary count was used to check if the windows is valid.

    public int LengthOfLongestSubstringTwoDistinct(string s) 
    {
        if(String.IsNullOrEmpty(s)) return 0;
        if(s.Length <= 2) return s.Length;
        
        Dictionary<char, int> dict = new Dictionary<char, int>();
        
        int left = 0, gLeft = 0, gLen = int.MinValue, k = 2;
        for(int right = 0; right < s.Length; right++)
        {
            if(!dict.ContainsKey(s[right])) dict[s[right]] = 1;
            else dict[s[right]]++;
            
            while(dict.Count() > k)
            {
                if( --dict[s[left]] == 0) dict.Remove(s[left]);
                
                left++;
            }
            
            int len = right - left + 1;
            if((right == s.Length - 1 || dict.Count == k) && len > gLen)
            {
                gLen = len;
                gLeft = left;
            }
        }
        
        Console.WriteLine("\"{0}\" is the longest substring with {1} distinct chars", s.Substring(gLeft, gLen), k);
        return gLen;
    }

Log in to reply
 

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