Minimum Window Substring

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Have you met this question in a real interview? 

Yes

Example

source = "ADOBECODEBANC" target = "ABC" Minimum window is "BANC".

Note

If there is no such window in source that covers all characters in target, return the emtpy string "".

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

Challenge

Can you do it in time complexity O(n) ?

Clarification

Should the characters in minimum window has the same order in target?

    - Not necessary.

public class Solution {

    /**

     * @param source: A string

     * @param target: A string

     * @return: A string denote the minimum window

     *          Return "" if there is no such a string

     */

    public String minWindow(String source, String target) {

        // write your code

        

        int[] needing = new int[256];

        int[] hasFound = new int[256];

        

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

            needing[target.charAt(i)]+=1;

        }

        

        int start = 0, count = 0, minCount = Integer.MAX_VALUE;

        String minWindow = "";

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

            if(needing[source.charAt(i)] == 0) continue;

            char c = source.charAt(i);

           

             hasFound[c]++;

            if(hasFound[ source.charAt(i)] <= needing[ source.charAt(i)]){

                count++;

            }

            if(count == target.length()){

                while(hasFound[source.charAt(start)] == 0 || needing[source.charAt(start)] < hasFound[source.charAt(start)]){

                    

                    if(needing[source.charAt(start)] < hasFound[source.charAt(start)]){

                        hasFound[source.charAt(start)]--;

                    }

                    start++;

                    

                }

                if(i-start+1 <  minCount){

                    minCount = i-start+1;

                    minWindow = source.substring(start, i+1);

                }

               

                

            }

        }

        return minWindow;

        

    }

}

public class Solution {
    /**
     * @param source: A string
     * @param target: A string
     * @return: A string denote the minimum window
     *          Return "" if there is no such a string
     */
    public String minWindow(String source, String target) {
        // write your code
        
        HashMap<Character, Integer> hasToFind = new HashMap<Character, Integer>();
        
        for(int i = 0; i < target.length(); i++){
            char c = target.charAt(i);
            if(hasToFind.containsKey(c)){
                 hasToFind.put(c, hasToFind.get(c)+1);
            } else{
                 hasToFind.put(target.charAt(i),1);
            }
               
        }
        
        int start = 0, count = 0, minCount = Integer.MAX_VALUE;
        String minWindow = "";
        for(int i = 0; i < source.length(); i++){
            
            char c = source.charAt(i);
            if(hasToFind.containsKey(c)){
            hasToFind.put(c, hasToFind.get(c)-1);
            if(hasToFind.get(c) >= 0) count++;
            
            while(count == target.length()){
                char d = source.charAt(start);
                if(hasToFind.containsKey(d)){
                    hasToFind.put(d, hasToFind.get(d)+1);
                    if(hasToFind.get(d) > 0){
                        if(i-start+1 <  minCount){
                            minCount = i-start+1;
                            minWindow = source.substring(start, i+1);
                        }
                        count--;
                    }
                } 
                start++;    
            }
                
        }}
        return minWindow;
        
    }

}