namespace _3_Smallest_Substring_Containing_The_Alphabet
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    public class EntryPoint
    {
        public static void Main(string[] args)
        {
            string sampleInput1 = "aaaaaabcdefghijklmnopqrstuvwxyz";
            string sampleInput2 = "abcdefghijklmn124345678!@#$%^&*opqrstuvwxyz!*abcdefghijklmn";

            Console.WriteLine(SmallestSubstringContainingTheAlphabet(sampleInput1)); // abcdefghijklmnopqrstuvwxyz
            Console.WriteLine(SmallestSubstringContainingTheAlphabet(sampleInput2)); // opqrstuvwxyz!*abcdefghijklmn
        }

        public static string MinWindow(string str, string word)
        {
            int[] needToFind = new int[256];
            int[] hasFound = new int[256];

            for (int i = 0; i < word.Length; ++i)
            {
                needToFind[word[i]]++;
            }

            int count = 0;
            int minWindowSize = int.MaxValue;
            int start = 0, end = -1;
            string window = "";

            while (++end < str.Length)
            {
                char c = str[end];
                if (++hasFound[c] <= needToFind[c])
                {
                    count++;
                }

                if (count < word.Length) continue;
                while (hasFound[str[start]] > needToFind[str[start]])
                {
                    hasFound[str[start++]]--;
                }

                if (end - start + 1 < minWindowSize)
                {
                    minWindowSize = end - start + 1;
                    window = str.Substring(start, end - start + 1);
                }
            }
            return window;
        }

        public static string SmallestSubstringContainingTheAlphabet(string str)
        {
            const string alphabet = "abcdefghijklmnopqrstuvwxyz";

            return MinWindow(str, alphabet);
        }
    }
}