# Minimum window substring which includes all the characters from substring

Posted on

Problem

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 less than the current min, it is updated, other wise the min window stays as it is.

After the iteration concludes, the current min is returned.

It will be great if somebody could take a look at my solution and let me know how I can improve it.

``````public class MinimumWindow{

static class Pair{
int start;
int end;
Pair(int start,int end){
this.start = start;
this.end = end;
}
}

private static int[] populateToFind(String target){
int[] toFind = new int[256];
for(char c:target.toCharArray()){
toFind[c] = toFind[c] + 1;
}
}

private static Pair findFirstWindow(String source,String target,int[] toFind,int[] currentlyFound){
int startIdx = -1;
for(int i=0;i<source.length();i++){
if(toFind[source.charAt(i)] > 0){
startIdx = i;
break;
}
}
if(startIdx == -1) return null;
int foundCount = 0;
int endIdx = startIdx;
for(int i=startIdx;i<source.length();i++){
if(foundCount == target.length()){
break;
}
char currentChar = source.charAt(i);
if(toFind[currentChar] > 0){
if(currentlyFound[currentChar] < toFind[currentChar]){
foundCount++;
}
currentlyFound[currentChar] = currentlyFound[currentChar] + 1;
endIdx = i;
}
}
if(foundCount < target.length()){
return null;
}
return new Pair(startIdx,endIdx);
}

private static boolean canMoveStart(int start,String source,int[] toFind,int[] currentlyFound){
return ((toFind[source.charAt(start)]==0)
|| (currentlyFound[source.charAt(start)] > toFind[source.charAt(start)]));
}

private static String minimumWindow(String source,String target){
if(target.length() > source.length()){
return "";
}

int[] toFind = populateToFind(target);
int[] currentlyFound = new int[256];

Pair w = findFirstWindow(source,target,toFind,currentlyFound);
if(w == null){
return "";
}

int start= w.start;
int end = w.end;
Pair min = w;
while(start < end){
if(canMoveStart(start,source,toFind,currentlyFound)){
if(toFind[source.charAt(start)] > 0){
currentlyFound[source.charAt(start)] = currentlyFound[source.charAt(start)] - 1;
}
start++;
}else{
if(end < source.length()-1){
if(toFind[source.charAt(end+1)] > 0){
currentlyFound[source.charAt(end+1)] = currentlyFound[source.charAt(end+1)] + 1;
}
end++;
} else {
break;
}
}
if(Math.abs(end - start) < Math.abs(min.end - min.start)){
min = new Pair(start,end);
}

}
return source.substring(min.start,min.end+1);
}

public static void main(String[] args){
String source = "ADOBECODEBANC";
String target = "ABC";
System.out.println(minimumWindow(source,target));
}
}
``````

Solution

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.

### API

How would one use this class?
Since it’s “just” a solution for a challenge,
it might be easy to say “who cares, nobody will use this”,
but in general you can always count on one user:
the unit tester (a.k.a the first user of a program).

Most methods are private, only `main` is public.
But `main` is not intended for testing,
and in any case it’s not very useful anyway because it doesn’t use its parameters and performs a simple hardcoded operation.

To make the class testable, simply make `minimumWindow` public.

Another odd element of the API is that `Pair` is not private.
It’s a minor thing,
but since you made all other methods private,
this one sticks out a bit.

The code is hard to read, in many ways.

Repeated long-ish expressions.
For example here:

``````private static boolean canMoveStart(int start,String source,int[] toFind,int[] currentlyFound){
return ((toFind[source.charAt(start)]==0)
|| (currentlyFound[source.charAt(start)] > toFind[source.charAt(start)]));
}
``````

The expression `source.charAt(start)` is used 3 times there.
It’s long, and it makes the condition long too and hard to read.
By extracting it to a local variable,
you could make the boolean expression shorter and easy to read,
and less error prone, like this:

``````private static boolean canMoveStart(int start, String source, int[] toFind, int[] currentlyFound) {
char startChar = source.charAt(start);
return toFind[startChar] == 0 || currentlyFound[startChar] > toFind[startChar];
}
``````

Another benefit of extracting `source.charAt(start)` to a variable is that you save on the processing logic in `.charAt`. That method is more than just a simple access into an array: it also checks for boundaries.
Doing that repeatedly is wasteful.

As a matter of fact, the caller of this method also does a `.charAt`.
And since this method only uses a single character in `source`,
you could just get `source.charAt(start)` in the caller,
and pass just that character to this method instead of the entire `source`.

``````private static boolean canMoveStart(char startChar, int[] toFind, int[] currentlyFound) {
return toFind[startChar] == 0 || currentlyFound[startChar] > toFind[startChar];
}
``````

This writing style is too compact and hard to read:

``````    for(int i=0;i<source.length();i++){
``````

The recommended writing style is this:

``````    for (int i = 0; i < source.length(); i++) {
``````

``````        toFind[c] = toFind[c] + 1;
``````

It’s simpler and cleaner to use `++` (or the `+=` operator):

``````        toFind[c]++;
``````

### Method decomposition

Most of the methods are very long.
They could be decomposed to smaller methods,
so that they become easier to understand.
More on that in the next section.

Take for example this piece of code in `findFirstWindow`:

``````int startIdx = -1;
for(int i=0;i<source.length();i++){
if(toFind[source.charAt(i)] > 0){
startIdx = i;
break;
}
}
``````

This could be extracted to a method:

``````private static int findStartIndex(String source, int[] toFind) {
for (int i = 0; i < source.length(); i++) {
if (toFind[source.charAt(i)] > 0) {
return i;
}
}
return -1;
}
``````

So that you can replace the earlier snippet in `findFirstWindow` with this single line:

``````int startIdx = findStartIndex(source, toFind);
``````

Notice that method extraction has the added benefit of explaining what the snippet does, thanks to the descriptive method name.

When you start decomposing a large method to smaller pieces,
sometimes further, unexpected opportunities appear.
For example,
as I tried to extract the second part of `findFirstWindow`,
I arrived at this helper method:

``````private static int findIndex(String source, int[] toFind, int[] currentlyFound, int startIdx, int count) {
for (int i = startIdx, foundCount = 0; i < source.length(); i++) {
char currentChar = source.charAt(i);
if (toFind[currentChar] > 0) {
if (currentlyFound[currentChar] < toFind[currentChar]) {
++foundCount;
if (foundCount == count) {
++currentlyFound[currentChar];
return i;
}
}
++currentlyFound[currentChar];
}
}
return -1;
}
``````

The cool thing about this is that on closer look I realized that the previously extracted `findStartIndex` is no longer necessary.
This latter method can be reused for the same purpose,
reducing `findFirstWindow` to:

``````private static Pair findFirstWindow(String source, String target, int[] toFind, int[] currentlyFound) {
int startIdx = findIndex(source, toFind, currentlyFound, 0, 1);
if (startIdx == -1) {
return null;
}
int endIdx = findIndex(source, toFind, currentlyFound, startIdx + 1, target.length() - 1);
if (endIdx == -1) {
return null;
}
return new Pair(startIdx, endIdx);
}
``````

### Unit testing

Before refactoring your code aggressively with confidence,
I added a bunch of unit tests to cover my back.
This is a good practice I recommend, especially when working with non-trivial code.
Here are some examples using JUnit4 to get you started:

``````public class MinimumWindowTest {

private String solve(String s, String t) {
return MinimumWindow.minimumWindow(s, t);
}

@Test
public void test_ADOBECODEBANC_ABC() {