Minimum Window Substring hard

Problem Statement

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a" Output: "a" Explanation: The minimum window substring "a" includes 'a' from string t.

Steps:

1. Character Count: Create a map (or hash table) to store the frequency of each character in string t. This map will act as our target frequency count.
2. Sliding Window: Use a sliding window approach. Maintain two pointers, left and right, representing the start and end of the window in s.
3. Window Expansion: Expand the window by moving the right pointer. For each character added to the window, update the frequency count in a separate map (let's call it window_count).
4. Check for Match: After adding a character, check if window_count contains all characters from t with at least the required frequency (as specified in the target_count map). If it does, we have a valid window.
5. Window Contraction: If we have a valid window, try to minimize its size by moving the left pointer. Continue moving left as long as the window remains valid (i.e., window_count still contains all characters from t with sufficient frequency). Update the minimum window size and its starting index accordingly.
6. Continue Expansion and Contraction: Repeat steps 3-5 until the right pointer reaches the end of s.

Explanation:

The algorithm uses a sliding window technique with two pointers to efficiently find the minimum window substring. The crucial idea is to maintain a count of the characters in the current window and compare it with the target character counts. By expanding and contracting the window, we systematically explore all possible substrings. The use of maps allows for quick lookups of character frequencies, resulting in an optimized solution.

Code:

#include <iostream>
#include <string>
#include <map>

using namespace std;

string minWindow(string s, string t) {
    if (s.length() < t.length()) return "";

    map<char, int> target_count;
    for (char c : t) {
        target_count[c]++;
    }

    map<char, int> window_count;
    int left = 0;
    int right = 0;
    int required = target_count.size();
    int formed = 0;
    int min_window_len = INT_MAX;
    int min_window_start = 0;

    while (right < s.length()) {
        char c = s[right];
        window_count[c]++;

        if (target_count.count(c) && window_count[c] == target_count[c]) {
            formed++;
        }

        while (left <= right && formed == required) {
            if (right - left + 1 < min_window_len) {
                min_window_len = right - left + 1;
                min_window_start = left;
            }

            c = s[left];
            window_count[c]--;
            if (target_count.count(c) && window_count[c] < target_count[c]) {
                formed--;
            }
            left++;
        }
        right++;
    }

    return min_window_len == INT_MAX ? "" : s.substr(min_window_start, min_window_len);
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    cout << minWindow(s, t) << endl; // Output: BANC

    s = "a";
    t = "a";
    cout << minWindow(s, t) << endl; // Output: a

    s = "a";
    t = "aa";
    cout << minWindow(s, t) << endl; //Output: ""

    return 0;
}

Complexity:

• Time Complexity: O(S + T), where S is the length of string s and T is the length of string t. We iterate through s at most twice.
• Space Complexity: O(T), due to the maps used to store character counts. In the worst case, the size of the maps is proportional to the number of unique characters in t.