~/leetcode $ 76. Minimum-Window-Substring

Back after like half a year because of Aleck… (this was definitely not done on June 15 2026)…

First thoughts, I need to get the characters and the count from the string t and then make a sliding window over string s keeping track of the characters that are within the sliding window.

I am going to re-use the count map over the string t and just decrement from it to keep track of the characters in the window (so that we just need to check that all the character count is 0 for the answer to be valid)

In the loop:

• add the current right element into the window
• if this element brings the char_count to negative, then we try to shift the leftmost pointer, stopping when the left pointer is about to delete a character we need.
• we continue this while keeping track of the minimum length of a valid answer.

One mistake that I made was in my validAnswer function where I was checking if all the counts was 0 but it should check if the count is less than or equal to 0 (even if the counts are negative, it should be still a valid answer).

After submitting the solution, I realized there was smarter way of doing this where instead of storing the minimum string (and using unnecessary space), we can instead store the starting index and the length of the min string. This would allow us to reconstruct the min string at the end of the function rather than creating strings unnecessarily.

One learning here was that cpp’s string.substr(startIndex, length) takes the starting index and the length of the substring instead of the starting index and the ending index. This threw me off so hard…

class Solution {
private:
    int validAnswer(unordered_map<char, int> &char_map) {
        for (auto p: char_map) {
            if (p.second > 0) {
                return 0;
            }
        }
        return 1;
    }

public:
    string minWindow(string s, string t) {
        unordered_map<char, int> t_char = {};
        for (char c: t) {
            t_char[c]++;
        }
        for (auto p: t_char) {
            cout << p.first << ' ' << p.second << '\n';
        }

        int startingIndex = 0;
        int length = std::numeric_limits<int>::max();
        int left = 0;
        int right = 0;

        while (right < s.length()) {
            char current_char = s[right];
            if (t_char.contains(current_char)) {
                --t_char[current_char];
                while (left < right) {
                    char tmp_char = s[left];
                    if (t_char.contains(tmp_char)) {
                        if (t_char[tmp_char] < 0) {
                            ++t_char[tmp_char];
                        } else {
                            break;
                        }
                    }
                    ++left;
                }
                if (validAnswer(t_char)) {
                    if (right - left + 1 < length) {
                        startingIndex = left;
                        length = right + 1 - left;
                    }
                }
            }
            ++right;
        }

        if (length == std::numeric_limits<int>::max()) { return ""; }
        return s.substr(startingIndex, length);
    }
};

Time Complexity: O(m + n)

Space Complexity: O(n)

Time Taken: 26m 57s