LC 76. Minimum Window Substring

Sarthak Sehgal · May 25, 2020

hard   strings

Two pointer approach basic idea:

  1. Create an unordered_map<char, int> freq_t which keeps track of frequency of each character of string T
  2. Keep two pointers l and r using which you iterate through the string S. Keep extending pointer “r” while keeping a track of count of characters encountered in a map unordered_map<char, int> freq_s.
  3. At each step, compare freq_s and freq_t. When freq_t is a subset of freq_s, i.e., each letter in freq_t is there in freq_s with same or more frequency, we know that the substring l to r is valid. At this point, start moving l towards r and comparing freq_t and freq_s at each step.

The above idea is great but comparing the two maps at each step can be an expensive operation. Especially when string T has a lot of unique characters. Fortunately, we can optimize it simply by keeping a track of “uniqueCharacters” in string T, which is essentially equal to size of map freq_t. See the code implementation below which implements the optimized approach:

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> freq_t;
        for (char c : t)
            freq_t[c]++;

        int unique = freq_t.size(), uniqTillNow = 0;
        int l = 0, r = 0, st = 0;
        int size = INT_MAX;

        unordered_map<char, int> freq_s;

        while (r<s.length()) { // r is the right limit of the two pointer approach
            freq_s[s[r]]++;

            if (freq_t[s[r]] == freq_s[s[r]]) // when the string s[l..r] has frequence of a character equal to that in string T, increase the uniquer char count
                uniqTillNow++;

            while (l<=r && uniqTillNow == unique) { // if uniqueTillNow==unique, we know that string freq_t is a subset of freq_s to let's try shortening the string s[l..r]
                if (r-l+1 < size) {
                    st = l;
                    size = r-l+1;
                }
                freq_s[s[l]]--;
                if (freq_s[s[l]] < freq_t[s[l]])
                    uniqTillNow--;
                l++;
            }

            r++;
        }

        return size == INT_MAX ? "" : s.substr(st, size);
    }
};

Time complexity: O(n)
Space complexity: O(n+m) where n is the length of string s and m is the length of string t

Twitter, Facebook