Solution for: Minimum window in String in O(n) | My Developed World
What I've personally found tricky in this problem was to realize the algorithm. I tried to imagine, without writing, a solution. I tried to imagine the string, the chars, the indexes to keep track of the windows, and so on. This way, I couldn't even think about a naive O(n^2) solution. I was stuck.
What can we do when we are stuck on a problem? Have a break. Try to free our mind for a little while. Have some fun/relaxing activities and in the end come back to break the problem down, armed with pen and paper. Yes, pen and paper. Drawing an instance of the problem is the best way to catch what we are missing, moreover breaking a problem in smaller part is the best way to focus on different aspects of the problem, without get stuck blinded from the whole complexity.
Let's start from the smallest unit of the problem question: the window. What exactly is a window in this context? A window in this context is a string itself. It is a subset of the input string S, which contains all the chars in T. An important property of a window is how its edges are defined, this is the keystone of the problem, and as long as I had not realized/formalized it, I could not solve the problem.
The figure above shows two examples of window over S given T. Focusing on the edges of these two windows,we can easily see that they are chars from the set T. So, the window is always bounded by two different characters of T and, if we imagine to scroll the string S from left to right, once we have found all the chars in T, we know that we have found a window and this windows can be calculated as all the chars of S between the "furthest" char of T from the current position and the char of T we just found at the current position (the closest).
Read full article from Solution for: Minimum window in String in O(n) | My Developed World
No comments:
Post a Comment