Minimum window substring

Problem

Brute force approach:
TC: O(N^2), SC: O(256) which is constant
Note: This will lead to TLE

class Solution {
    public String minWindow(String s, String t) {


        int min = Integer.MAX_VALUE;
        int start =-1;
        int end = -1;
        //generating all possible substrings and returning the smallest substring having
        //all the character of string t
        for(int i =0;i<s.length();i++){
            int arr[] = new int[256]; // all the asci characters
            //initialize arr with count of character in t
            for(int  k =0;k<t.length();k++){
                arr[t.charAt(k)]++;
            }
            int count =0;
            for(int j =i;j<s.length();j++){
            // if character at j in s is also present in t, increase count
                if(arr[s.charAt(j)] >0){
                    count++;
                }
                arr[s.charAt(j)]--;//decrease the frequency of s.charAt(j) by 1 in arr
                if(count ==t.length()){// if count == length of t we have found one potential substring 
                    if(min> j-i+1){
                        min  = j-i +1;
                        start  = i;
                        end = j;
                    }
                    break;// break out as there is no need to propagate further in the current iteration
                }
            }
        }
        if(start ==-1 || end ==-1) return "";// if not found 
        return s.substring(start,end+1);// else
    }
}

---

Optimal approach:
TC: O(n) , SC:O(256) wich is constant

// this intuition will require solving such problems as much as possible
class Solution {
    public String minWindow(String s, String t) {
        int left=0,right=0;
        int min = Integer.MAX_VALUE;
        int count =0;
        int arr[] = new int[256]; // has table for keeping count of characters
        // keeping track of start and end index
        int start =-1;
        int end = -1;
        for(int i=0;i<t.length();i++){
            arr[t.charAt(i)]++;
        }
        while(right<s.length()){
            char c = s.charAt(right);
            if(arr[c]>0){ // if the character is part of t, then increment count
                count++;
            }
            arr[c]--;// decrease the count of the character in the hash table once it is taken into consideration 
            while(count ==t.length()){ // if count == t.size() we have found a potential window
                if(min > right-left+1){
                    min = right-left+1;
                    //update the start and end accordingly 
                    start = left;
                    end = right;
                }
                arr[s.charAt(left)]++;//since we are removing this character from window and increasing the left pointer to point to next character after this, there will be one less
                //character that is not part of the t 
                if(arr[s.charAt(left)]>0){ // if after doing +1 for arr[s.charAt(left)] character, if it become positive then it will mean that this was part of t, and now we will have to look for this character in the next window 
                    count--; // since this was part of t, then count should decrement by 1
                }
                left++;
            }
            right++;
        }
        if(start ==-1 || end ==-1) return "";
        return s.substring(start,end+1);
    }
}

The above is the detailed content of Minimum window substring. For more information, please follow other related articles on the PHP Chinese website!