[Google][GeeksForGeeks] Longest substring with k unique characters

Problem: Given a string you need to return longest possible substring that has exactly K unique characters. If there is more than one substring of longest possible length, then print any one of them. If there are no such substring, return empty string.

Example:

Input: str = "aabbcc", k = 2
Output: "aabb"
Explanation: Can return "bbcc"

Approach: This is a straight forward sliding window problem. We can use a map to maintain the characters and their count in the current window. Whenever the number of keys in the map are equal to the k, we can check if current window length is more than max length then we can update the max length.

if length of current window is more than k then we need to slide the window from the left. That's all!

Implementation in C#:

    private static string MaxSubstringWithKUniqueChars(string str, int k)

    {

        int length = str?.Length ?? 0;

        if (length < k)

        {

            return "";

        }     

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

        int start = 0, maxLength = 0, startIndex = -1;

        for (int end = 0; end < length; ++end)

        {

            if (!freqMap.ContainsKey(str[end]))

            {

                freqMap[str[end]] = 0;

            }

            ++freqMap[str[end]];

            if (freqMap.Count == k)

            {

                int currLength = end - start + 1;

                if (maxLength < currLength)

                {

                    maxLength = currLength;

                    startIndex = start;

                }

            }

            while (freqMap.Count > k)

            {

                --freqMap[str[start]];

                if (freqMap[str[start]] == 0)

                {

                    freqMap.Remove(str[start]);

                }

                ++start;

            }

        }

        return startIndex != -1 ? str.Substring(startIndex, maxLength) : "";

    }

Complexity: O(n)