Leetcode Study Day 16

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
 

Constraints:

m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.

My solution

I write specific comments in my code

class Solution {
public:
    string minWindow(string s, string t) {
        // A map to store chars with their appears number
        unordered_map <char, int> charCount;
        for (int i = 0; i < t.size(); i++)
            charCount[t[i]] ++;
        int left = 0, right = 0, counter = t.size(), minStart = 0, minLen = INT_MAX;
        while (right < s.size()){
            // if the character in s is in t, we decrease the counter
            if (charCount[s[right]] > 0)
                counter --;
            // Then we decrease the appears number which is stored in the map
            charCount[s[right]] --;
            // we move the right pointer
            right ++;
            // counter equals to 0 means we find a fixed window
            while (counter == 0){
                // we update the minimum length of the substring, and the minStart
                if (right - left < minLen){
                    minLen = right - left;
                    minStart = left;
                }
                // Try to move window to the right position
                charCount[s[left]]++;
                // If it is greater than 0, means s[left] is in t, we need increase the counter
                if (charCount[s[left]] > 0)
                    counter ++;
                // We move the left pointer
                left ++;
            }
        }
        // return the substring is minLen is not MAX
        if (minLen != INT_MAX)
            return s.substr(minStart, minLen);
        return "";
    }
};