Minimum window substring which includes all the characters from substring

I recently came across this problem which is as follows:


Given a string S and a string T, find the minimum window in S which
will contain all the characters in T in complexity O(n).


For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".


Note: If there is no such window in S that covers all characters in T,
return the emtpy string "".


If there are multiple such windows, you are guaranteed that there will
always be only one unique minimum window in S.

My solution first finds the first window which contains all the characters in T.

It does it by first creating a lookup called toFind (array of int[256]) containing the counts for all the characters in T.

It maintains another lookup of int[256] called currentlyFound in which it stores the count of all the characters it has found so far.

While iterating through the characters of S, the algorithm keeps track of all the characters encountered so far, if all the characters of T have been encountered during the first scan, the algorithm will return the offsets for the first window and store it as the current minimum window.

The next steps will try to increment the 'begin' or 'end' until the next minimum window has been discovered.

The begin is incremented only if the number in currentlyFound for character at index begin is greater than the number of characters in toFind for index begin, since this way the invariant of the window having at least the total number of characters in T will not be disrupted.

The begin is also incremented when the character it points to is not contained in toFind.

If begin cannot be incremented, then end is incremented until it cannot be incremented anymore. While the end is incremented, the currrentlyFound for the char it points to is incremented.

This goes on until the offsets cannot be incremented anymore. Every time a window is found, the size of its offsets is compared to the current min. If it is les

After seen this question, I had the feeling it could be better with more OO programming.

So I started to create mine own way, with more OO, less code and easier to read.

I was happy with mine result until I did benchmark it with your code.

Result of 1000000 iterations :


new method :

BAANC

Total execution time: 4527ms

original method :

BAANC

Total execution time: 480ms

So I'm really not going to speak that way, you are coding smart with primitives, what's also the reason of the benchmark result explains.

There are a few points what could be improved.

At first sight, I didn't understand why you create arrays of 256 size.

After a better look, I understand it but please use a constant for this and name it like MAX_ASCII_VALUE_CHARACTER.

While they do not speak over what characters the String could contain, I'm tending more to go to the original ASCII table and not the extended, so I would change it to 123(z) or 128(full).

Your naming of variable is pretty good, but sometimes you still name them bad.

Example : Pair w or Pair min.

While the min is already slightly better chosen, you could still name it like currentMinPair and the other one, you actually don't need it.

You can assign the result directly to min, check min for null and read start and end from min pair.

The reason is that you don't use w further in your code.

So final conclusion for me :

Pretty good and smart code, with some (very minor) points to improve.

StackExchange Code Review Q#104689, answer score: 6