Leetcode 76: Minimum Window Substring

June 30, 2017

Introduction

Leetcode 76 minimum windows substring is such a popular algorithm, Julia was asked to work on the algorithm in mocking experience, the peer likes Julia to work on the string algorithm, and the peer gave the advice that Julia's solution will have time out issue.

Algorithm study 

Mocking 8:00 pm - 8:30 pm

Here is the C# practice in mocking experience, the code has timeout issue. Time complexity should be cut down.

Here is the C# practice to pass online judge of Leetcode 76.

Leetcode Discussion

Read one of discussions - link is here.

Need to write a short and better solution.

The current window is s[i:j] and the result window is s[I:J]. In need[c] I store how many times I need character c (can be negative) and missing tells how many characters are still missing. In the loop, first add the new character to the window. Then, if nothing is missing, remove as much as possible from the window start and then update the result.

Julia is very good at writing the code, she just need a good idea to work on.

C# code is rewritten, link is here.

What can I say after I debug the code using a test case? This code is hard to understand, one dictionary serves multiple purposes. It reminds me the algebra.

For example, "xxyz", search string is "xyz".
We can keep the search string in the dictionary<char, int>
dict['x'] = 1,
dict['y'] = 1,
dict['z'] = 1

Now, we like to use those values to track how many in the sliding window. If the sliding window is "xx", then dict['x'] = -1. If the value is 0, then the number of char is exactly what need. -1 means that there is extra one.

We also keep count of how many chars we need in search string. First visit of x in sliding window "xx" we increment count variable once, but second one we do not do that. In other words, there is only one 'x' in search string. From any iteration, it is easy to tell if the sliding window contains the search string by comparing count variable with the length of search string.

Queue is not necessary, just track the left position of sliding window. One advantage to use queue is to filter out characters not in the search string.

Move Queue from the code, and come back to work on the algorithm later.

Most important is to check time complexity of this idea, it is better than O(s.Length * t.Length), actually it is O(s.Length).