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 to update when moving right
2. Under what circumstances should right stop expanding and start moving left to shrink the window
3. What data to update when moving left
4. Should we update the result when expanding the window or when 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 window left
			}
		}
		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 "";
        }
};