using System;

using System.Collections.Generic;

​

/* terminating cases:

-reach end of string

​

-save the first and last index of the sliding window (i, j)

-if j is k+1 unique character, then, increment i

*/

public class Program

{

    public static void Main()

    {

        Console.WriteLine(FindSubstring("abbabbaccaaddaakk", 4));

    }

    public static string FindSubstring(string input, int requiredNumUniqueChars)

    {

        if (string.IsNullOrWhiteSpace(input) || input.Length < requiredNumUniqueChars)

            return string.Empty;

        int startIndex = 0;

        int endIndex = 0;

        var uniqueCharsFound = new Dictionary<char, int>();

        int resultStartIndex = 0;

        int resultEndIndex = 0;

        while (endIndex < input.Length)

        {

            if (IsUniqueChar(input[endIndex], uniqueCharsFound, requiredNumUniqueChars))

            {

                AddChar(input[endIndex], uniqueCharsFound);

                // expand the window

                endIndex++;

            }

            else

            {

                // save current substring window if it's the longest encountered so far

                // of the requiredNumUniqueChars

                if (uniqueCharsFound.Count == requiredNumUniqueChars

                    && (resultEndIndex - resultStartIndex)  < (endIndex - 1 - startIndex))

                {

                    resultStartIndex = startIndex;

                    resultEndIndex = endIndex - 1;

                }

                // shrink the window

                RemoveChar(input[startIndex], uniqueCharsFound);

                startIndex++;

            }

        }

        if (uniqueCharsFound.Count < requiredNumUniqueChars)

            return string.Empty;

            //return "not enough uniqueCharsFound.  uniqueCharsFound.Count: " + uniqueCharsFound.Count;

        if (endIndex == input.Length)

            endIndex--;

        // if the entire input string is the longest substring then return it

        if ((resultEndIndex - resultStartIndex)  < (endIndex - startIndex))

            return input.Substring(startIndex, endIndex - startIndex + 1);

            //return "startIndex: " + startIndex + ", endIndex: " + endIndex;

        //Console.WriteLine("resultStartIndex: " + resultStartIndex + ", resultEndIndex: " + resultEndIndex);

        return input.Substring(resultStartIndex, resultEndIndex - resultStartIndex + 1);

    }

    public static bool IsUniqueChar(char input, Dictionary<char, int> uniqueCharsFound, int requiredNumUniqueChars)

    {

        return (!uniqueCharsFound.ContainsKey(input)) 

            ? uniqueCharsFound.Count < requiredNumUniqueChars

            : true;

    }

    public static void AddChar(char input, Dictionary<char, int> uniqueCharsFound)

    {

        if (!uniqueCharsFound.ContainsKey(input))

        {

            //Console.WriteLine("adding uniqueChar " + input);

            uniqueCharsFound[input] = 1;

        }

        else

        {

            //Console.WriteLine("incrementing uniqueChar " + input);

            uniqueCharsFound[input] = uniqueCharsFound[input] + 1;

        }

    }

    public static void RemoveChar(char input, Dictionary<char, int> uniqueCharsFound)

    {

        if (!uniqueCharsFound.ContainsKey(input))

            return;

        if (uniqueCharsFound[input] == 1)

        {

            //Console.WriteLine("removing uniqueChar " + input);

            uniqueCharsFound.Remove(input);

        }

        else

        {

            uniqueCharsFound[input] = uniqueCharsFound[input] - 1;

        }

    }

}