Minimum Window Substring

Problem

Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

Examples

Example 1:

Input: s = "OUZODYXAZV", t = "XYZ"

Output: "YXAZ"

Example 2:

Input: s = "xyz", t = "xyz"

Output: "xyz"

Example 3:

Input: s = "x", t = "xy"

Output: ""

Constraints

• 1 <= s.length <= 1000
• 1 <= t.length <= 1000
• s and t consist of uppercase and lowercase English letters.

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string s and m is the number of unique characters in s and t.

Solution

We count how many of each char we need for the input t, and we track how many individual chars have their count met. We start with a sliding window [left, right]. An outer loop moves the right window forward. We track the counts of each char in the current window, and check if we now just matched a required count (make sure to not over count, only check at equality). We then walk the left end of the window forward while the chars_met_count is valid, checking if we found a shorter substring using the length of the window. We remove the char, update the counts, then walk the left index forward.

class Solution {
public:
    string minWindow(const string &s, const string &t) {
        std::unordered_map<char, int> t_counts;
        // Char counts in t
        for (const auto &c : t) {
            ++t_counts[c];
        }
        const auto num_chars_meet_needed = static_cast<int>(t_counts.size());
 
        std::size_t left = 0;
        std::unordered_map<char, int> window_counts;
        int num_chars_meet_count = 0;
        std::size_t result_len = std::numeric_limits<std::size_t>::max();
        std::size_t res_idx_left = 0;
        std::size_t res_idx_right = 0;
        // Walk sliding window right
        for (std::size_t right = 0; right < s.size(); ++right) {
            const char c = s[right];
            ++window_counts[c];
            // If we now match required count, track number of chars meeting count
            if (t_counts.contains(c) && window_counts[c] == t_counts[c]) {
                ++num_chars_meet_count;
            }
 
            // Walk window left while window is valid, seeing if we find new smallest window
            while (num_chars_meet_count == num_chars_meet_needed) {
                const char c_removed = s[left];
                // Check for better substr
                if (right - left + 1 < result_len) {
                    result_len = right - left + 1;
                    res_idx_left = left;
                    res_idx_right = right;
                }
 
                // If removing char moves below required count, update tracker
                if (t_counts.contains(c_removed) && window_counts[c_removed] == t_counts[c_removed]) {
                    --num_chars_meet_count;
                }
                --window_counts[c_removed];
                ++left;
            }
        }
        return result_len == std::numeric_limits<std::size_t>::max() 
                        ? "" 
                        : s.substr(res_idx_left, result_len);    
    }
};