Interview Classic 150 Questions P76 Minimum Window Substring

---

Timeline

Timeline

2025-11-14

init

Sliding window

---

Problem:

P76 Minimum Window Substring

https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-interview-150

Sliding window:
window[left, right], consider the following questions:

1. What data should be updated when moving right?
2. Under what circumstances should right stop expanding and start moving left to shrink the window?
3. What data should be updated when moving left?
4. Should the result we want be updated when expanding the window or shrinking the window?

#include <string>
#include <unordered_map>

using std::unordered_map;
using std::string;

class Solution {
    public:
	string minWindow(string s, string t)
	{
		int i = 0, j = 0, n = s.size();
		int start;
		int min_len = n + 1;
		int valid = 0;
		unordered_map<char, int> need;
		unordered_map<char, int> window;

		for (char &ch : t)
			need[ch]++;

		for (j = 0; j < n; j++) {
			if (!need.count(s[j]))
				continue;

			window[s[j]]++;

			if (window[s[j]] == need[s[j]])
				valid++;

			while (valid == need.size()) { // Shrink left
				if (j - i + 1 < min_len) {
					start = i;
					min_len = j - i + 1;
				}
				if (need.count(s[i])) {
					if (window[s[i]] == need[s[i]])
						valid--;

					window[s[i]]--;
				}
				i++; // Move the left pointer
			}
		}
		return min_len == n + 1 ? "" : s.substr(start, min_len);
	}
};

leetcode hot 100 rewrite

#include <string>
#include <unordered_map>

using std::string;
using std::unordered_map;

class Solution {
    public:
        string minWindow(string s, string t)
        {
                int slen = s.size(), tlen = t.size();
                int left = 0, right = 0;
                int valid = 0, total_valid = 0;
                int min_len = slen + 1, res_start = 0;
                unordered_map<char, int> need, window;

                if (tlen > slen)
                        return "";

                for (char ch : t)
                        need[ch]++;

                total_valid = need.size();

                while (right < slen) {
                        window[s[right]]++;
                        if (window[s[right]] == need[s[right]])
                                valid++;
                        right++;

                        while (left < right && valid >= total_valid) { // Shrink

                                if (right - left < min_len) {
                                        min_len = right - left;
                                        res_start = left;
                                }

                                if (window[s[left]] == need[s[left]])
                                        valid--;

                                window[s[left]]--;

                                left++;
                        }
                }
                if(min_len != slen+1)
                        return s.substr(res_start, min_len);
                else
                        return "";
        }
};