C++: Minimum Window Substring

Thought Process

To find the minimum window substring in 's' that contains all characters of 't', we use a sliding window approach. We maintain a frequency hash for characters in 't' and track the number of characters still needed in the current window. As we expand the window by moving the end pointer, we decrement the frequency of characters in the hash. When all required characters are included, we try to shrink the window from the start to find the smallest valid window. This ensures we efficiently find the minimum window containing all characters of 't'. 

class Solution {
public:
    string minWindow(string s, string t) {

        int tHash[130]={0};
        for(int i=0;i<t.size();i++){

            char ch = t[i];
            tHash[ch]++;  
        }

        int start = 0;
        int end = 0;
        int elementsNeedsToBeAddedInWindow = t.size();
        int mnLength = INT_MAX;
        int startingIndex = 0;
        bool windowExist = false;
        string result;

        while(end<s.size()){

            char ch = s[end];
            tHash[ch]--;

            if(tHash[ch]>=0) 
                elementsNeedsToBeAddedInWindow--;

            while(elementsNeedsToBeAddedInWindow==0){

                windowExist = true;
                int lengthOfSubstring = end-start+1;
                if(lengthOfSubstring<mnLength){
                    mnLength = lengthOfSubstring;
                    startingIndex = start;
                }
                char ch1 = s[start];
                tHash[ch1]++; // -1 --> 0 

                if(tHash[ch1]>0){ 
                    elementsNeedsToBeAddedInWindow++;
                }
                start++;
            }
            end++;
        }
        if(windowExist)
            return s.substr(startingIndex,mnLength);
        else
            return "";
    }
};

Code Complexity

Time Complexity: O(n + m)

The algorithm iterates through 's' and 't' once, where 'n' is the length of 's' and 'm' is the length of 't'.

Space Complexity: O(1)

The algorithm uses a fixed-size frequency hash, ensuring constant space usage.

Code copied!