# O(n) Solution Using a Custom QueueWrapper

• 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))
{
++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;
}
}
``````

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