0076-minimum-window-substring.cs

publicclassSolution
{

publicstringMinWindow(strings,stringt)

{
if(string.IsNullOrEmpty(t))returnstring.Empty;

varcountT=newDictionary<char,int>();
varwindow=newDictionary<char,int>();

foreach(varcint)
{
AddCharToDictionary(c,countT);
}

varhave=0;
varneed=countT.Count;
varleft=0;
varres=new[]{-1,-1};
varresultLength=int.MaxValue;
for(varright=0;right<s.Length;right++)
{
varc=s[right];
AddCharToDictionary(c,window);

if(countT.ContainsKey(c)&&window[c]==countT[c])have++;

while(have==need)
{
// update our result
varwindowSize=right-left+1;
if(windowSize<resultLength)
{
res=new[]{left,right};
resultLength=windowSize;
}

// pop from the left of our window
window[s[left]]--;
if(countT.ContainsKey(s[left])&&window[s[left]]<countT[s[left]])
{
have--;
}

left++;
}
}

returnresultLength==int.MaxValue
?string.Empty
:s.Substring(res[0],res[1]-res[0]+1);
}

privatevoidAddCharToDictionary(charc,IDictionary<char,int>dict)
{
if(dict.ContainsKey(c))dict[c]++;
elsedict.Add(c,1);
}
}