03 Nov 2023•C++•Unknown

Minimum Window Substring

notes and solution files for minimum window substring.

this entry collects the solution files i have for minimum window substring. i may expand it with a fuller write-up later, but the implementation files are already here.

available solution files

C++ minimum-window-substring/solution.cpp

Solution files

C++•minimum-window-substring/solution.cpp

class=class="syntax-string">"syntax-comment">#include <string>
class=class="syntax-string">"syntax-comment">#include <unordered_map>
class=class="syntax-string">"syntax-comment">#include <climits>

using namespace std;

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

        int required_count = target_count.size();

        int left = class="syntax-number">0, right = class="syntax-number">0;
        int formed = class="syntax-number">0;
        unordered_map<char, int> window_counts;
        int min_len = INT_MAX;
        string min_window = class="syntax-string">"";

        while (right < s.length()) {
            char char_right = s[right];
            window_counts[char_right]++;
            if (target_count.count(char_right) && window_counts[char_right] == target_count[char_right])
                formed++;

            while (formed == required_count && left <= right) {
                char char_left = s[left];
                if (right - left + class="syntax-number">1 < min_len) {
                    min_len = right - left + class="syntax-number">1;
                    min_window = s.substr(left, min_len);
                }

                window_counts[char_left]--;
                if (target_count.count(char_left) && window_counts[char_left] < target_count[char_left])
                    formed--;
                left++;
            }

            right++;
        }

        return min_window;
    }
};