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;        }        return toFind;    }    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));    }}
Minimum window substring which includes all the characters from substring
java;algorithm;programming challenge
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: 480msSo 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.