/*

Find the shortest string in a given string that contains all the characters of a given word

input1: My Name is Fran

input2: rim

*/

using System;

public class Program

{

    public string GetSubstring(string input1, string input2)

    {

        int len1 = input1.Length;

        int len2 = input2.Length;

        if(len1 < len2)

        {

            return " ";

        }

        int[] hash_pat = new int[256];

        int[] hash_str = new int[256];

        for (int i = 0; i < len2; i++)

        {

            hash_pat[input2[i]]++;

        }

        int start = 0, start_index = -1, min_len = int.MaxValue;

        int count = 0;

        for (int j = 0; j < len1; j++)

        {

            hash_str[input1[j]]++;

            if(hash_str[input1[j]] <= hash_pat[input1[j]])

                count++;

            if (count == len2)

            {

                while(hash_str[input1[start]] > hash_pat[input1[start]] || hash_pat[input1[start]] == 0)

                {

                    if (hash_str[input1[start]] > hash_pat[input1[start]])

                        hash_str[input1[start]]--;

                    start++;

                }

                int len_window = j - start + 1;

                if(min_len > len_window)

                {

                    min_len = len_window;

                    start_index = start;

                }               

            }

        }

        if(start_index == -1)

        {

            return " ";

        }

        return input1.Substring(start_index, min_len);

    }

    public static void Main()

    {

        Program p = new Program();

        Console.WriteLine(p.GetSubstring("My Name is Fran","rim"));

        Console.WriteLine(p.GetSubstring("I am the greatest","imt"));

    }

}