[Google][LintCode] Longest Substring with At Most K Distinct Characters

Problem: Given a string S, find the length of the longest substring T that contains at most k distinct characters.

Example:

Input: S = "eceba", k = 2
Output: 3 ("ece")

Input: S = "aa", k = 1
Output: 2 ("aa")

Approach: We will use Sliding Window approach here. We will increase the window till the number of unique characters in window is less than k. Obviously we will use a map here to keep track of it. We will also keep tracking of the max length by comparing the maxLength variable to the current window length.

Implementation in C#:

    public int LengthOfLongestSubstringKDistinct(string s, int k)

    {

        int start = 0, end = 0, maxLength = 0;

        Dictionary<char, int> charFreqMap = new Dictionary<char, int>();

        while (end < s.Length)

        {

            if (!charFreqMap.ContainsKey(s[end]))

            {

                charFreqMap[s[end]] = 0;

            }

            ++charFreqMap[s[end]];

            while (charFreqMap.Keys.Count > k)

            {

                --charFreqMap[s[start]];

                if (charFreqMap[s[start]] == 0)

                {

                    charFreqMap.Remove(s[start]);

                }

                ++start;

            }

            maxLength = Math.Max(maxLength, end - start + 1);

            ++end;

        }

        return maxLength;

    }

Complexity: O(n)