3-Smallest-Substring-Containing-The-Alphabet
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);
}
}
}