76. Minimum Window Substring

Link

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".

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

Solution

 public String minWindow(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        int[] map = new int[256];
        
        for(char c : tChars){
            map[c]++;
        }
        int count = tChars.length;
        int minStart = 0, minEnd = 0, start = 0, end = 0, minLength = Integer.MAX_VALUE;
        while(end < s.length()){
         
            if(map[sChars[end]] > 0){
                count--;
            }
            map[sChars[end]]--;
            
            while(count == 0){
                if((end - start + 1) < minLength){
                    minLength = end - start + 1;
                    minStart = start;
                    minEnd = end;
                }
                //trying to change the start index to start+1
                //if the current one is required by t string ie. it's value is 0
                if(map[sChars[start]] == 0){
                    count++;
                }
                map[sChars[start]]++; //add back the value in map whitch index is the sChar[start]
                start++;
            }
            end++;
        }
        if( minLength == Integer.MAX_VALUE) //i.e not found
            return "";
        return s.substring(minStart, minStart+minLength);
    }