Annotated solution using a char frequency map and 2 pointers


  • 0
    L

    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))
    		{
    			charMap.Add(c, 1);
    		}
    		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)
    	{
    		return ""; // return empty if valid window not found
    	}
    
    	// else, return our best answer
    	return s.Substring(minWindowStart, minWindowLength);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.