Leetcode 76: Minimum Window Substring

My solution involves two pointers l and r to mark the begin and end of a sliding window. We will expand by incrementing r and shrink by incrementing l. So while we don’t have a complete window (complete in that it contains all the letters of t) we will expand and then while do have a complete window, we shrink. At every step we check if we have a complete window and if its positions are smaller than the previous one. If it is smaller then remember those positions in min_l and min_r. I implemented with two unordered_maps (one for the sliding window character frequencies and one for string t character frequencies).

I have seen it implemented with a single array where you initialise it to frequencies of chars in t and then you decrement those frequencies as you come across them in the window. When you get to zero then that means you’ve got the required amount. Less than 0 and you have more than the required amount and in that case you don’t add to count. That’s a clever solution but I think my one is more intuitive and easier to follow.

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.