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

A substring is a contiguous sequence of characters within the string.

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> v(128);
        for(auto& ch : t) v[ch]++;
        int counter = t.size(), distance = INT_MAX, start = 0, begin = 0, end = 0;
        while(end < s.length()) {
            if(v[s[end++]]-- > 0) counter--;
            while(!counter) {
                if(end - begin < distance) distance = end - (start = begin);
                if(v[s[begin++]]++ == 0) counter++;
            }
        }
        return distance == INT_MAX ? "" : s.substr(start, distance);
    }
};