O(n) Solution Using a Custom QueueWrapper


  • 0
    R

    I wrote a custom Queue Wrapper container which supports "DistinctCount" and "DequeueCount" in addition to standart Enqueue/Dequeue operations.

    We start scanning the chars in the string one-by-one and adding to the queue:
    1- Whenever there are k or less distinct chars in the queue, we're good.
    2- When the number of distinct chars in the queue reach k + 1, we dequeue until we reduce the number of distinct chars back to k.
    3- The number of dequeues will also be equal to the start index of the new string.
    4- Keep track of the max length during these operations

    Here's my code:

    public class Solution
    {
        class QueueWithCounts
        {
            Queue<char> queue = new Queue<char>();
            private Dictionary<char, int> mapCounts = new Dictionary<char, int>();
            int dequeueCnt = 0;
            public int distinctCount = 0;
    
            public void Enqueue(int index, char c)
            {
                queue.Enqueue(c);
    
                if (!mapCounts.ContainsKey(c))
                {
                    mapCounts.Add(c, 0);
                    ++distinctCount;
                }
    
                ++mapCounts[c];
            }
    
            public int Dequeue()
            {
                char cRemoved = queue.Dequeue();
    
                if (--mapCounts[cRemoved] == 0)
                {
                    mapCounts.Remove(cRemoved);
                    --distinctCount;
                }
    
                return ++dequeueCnt;
            }
        }
    
        public int LengthOfLongestSubstringKDistinct(string s, int k)
        {
            QueueWithCounts q = new QueueWithCounts();
            int max = 0;
            int substrStart = 0;
            for (int i = 0; i < s.Length; ++i)
            {
                char c = s[i];
                q.Enqueue(i, c);
    
                while (q.distinctCount > k)
                {
                    substrStart = q.Dequeue();
                }
    
                max = Math.Max(max, i - substrStart + 1);
            }
    
            return max;
        }
    }
    

Log in to reply
 

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