# Annotated solution using a char frequency map and 2 pointers

• This is the same solution as the top voted one that includes the template. I've changed variable names and heavily commented the code to make it easier to understand. I had a pretty tough time understanding what was going on and it wasn't until I did this and walked through slowly that I got the picture.

``````// find the min substring in s that contains ALL characters in t
static string MinWindowSubstring(string s, string t)
{
// initialize a dict that keeps track of all the characters, and their frequencies,
// that we need to find as we're going through s
var charMap = new Dictionary<char, int>();
foreach(char c in t)
{
if (!charMap.ContainsKey(c))
{
}
else
{
charMap[c]++;
}
}

int searchSize = s.Length;

// These are the pointers that we "slide" around while going through s
// when we find a valid window (that contains all chars in t), it may
// or may not be the best (minimum) window we've found. That of course,
// depends on the current values of minWindowStart and minWindowLength
int windowStart = 0;
int windowEnd = 0;

// Keeps a count of characters we need to find in order to have a valid window.
// As we slide our window and find a new character that needs to be included in
// the substring, we decrement this counter. When it's 0, it means that we've found
// a valid window.
// This also means that we only decrement this on characters that are both a part
// of t AND that we still need to find. For example, if t is "abbc" and we've already
// found 2 b's in our window and find another one, we DONT decrement this.
int counter = t.Length;

// These 2 variables hold the current best answer we've found, updated only
// when we find a better one (think greedy algorithm)
// minWindowLength is initialized as int's Max value such that the very first
// window we find is automatically the best one at that point
int minWindowStart = 0;
int minWindowLength = int.MaxValue;

// Both the window start and end pointers start at 0, and we begin by moving the end
// over until we find our first valid window
while (windowEnd < searchSize)
{
char currentChar = s[windowEnd];

// if the current char is required (part of t AND its frequency count is greater than 0),
// decrement the counter and also decrement its' value in the charMap
bool foundRequiredChar = charMap[currentChar] > 0;
if (foundRequiredChar)
{
counter--;
}

charMap[currentChar]--;

// slide the window end pointer over to continue searching
windowEnd++;

// if the counter is 0, that means we've found all required characters in this current
// window
// ** It's important that windowEnd is incremented before this check (keep reading to see why)
while (counter == 0)
{
// is the current window found a better answer? (ie does it have a smaller range?)
if (windowEnd - windowStart < minWindowLength)
{
// if so, update our answer (remember that this is a greedy algorithm)
// ** by keeping track of these 2 variables, at the end of our method,
//    we can return the correct window (substring) using minWindowStart
//    and minWindowLength as the string.Substring() arguments. Thus,
//    windowEnd must be incremented earlier before entering the while loop
//    so we get the correct length.
minWindowStart = windowStart;
minWindowLength = windowEnd - windowStart;
}

// now, we slide the window start pointer up 1 at a time until we hit a character
// that is required (part of t)

// we're removing the first item of the current window by sliding forward once, so
// we need to restore the correct value in charMap
char charBeingRemoved = s[windowStart];
charMap[charBeingRemoved]++;

// is this value that we're chopping off a required char in t? if so, increment
// the counter so our algorithm knows
if (charMap[charBeingRemoved] > 0)
{
counter++;
}

windowStart++;

// if the counter was incremented, this means that we now exit this while loop
// and again continue in the outer loop. We again continue sliding the window's
// end pointer outward until we the char we removed.

// Lets say s was "abcdddac" and t was "ac".
// Then, the first window we find is "abc".
// We chop off the first letter "a", and continue searching for the next valid
// window, which is "bcddda". This is not a better answer, so those variables aren't updated.
// however, we can do slightly better. This while loop will chop off the first char again, which
// is "b" and not required because it's not part of t. so the window's begin pointer is moved up again
// until it hits the first character required by t, which is "c".
// At this point, the valid window we found is "cddda", still not good enough to be the best answer, but
// this illustrates how this algorithm works.

// Every time we find a valid window, we keep sliding the beginning of the window forward until we can remove
// a character that is a part of t. Then, we keep sliding the end over until we find it.
}
}

if (minWindowLength == int.MaxValue)
{