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 atleast 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 the 'begin' cannot be incremented, the '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. Everytime 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.

Thanks

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));
    }
}