Minimum Window Substring hard

Problem Statement

Given two strings s and t, find 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:

• If there is more than one minimum window, you can return any one.

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 entire string s is the minimum window.

Steps

1. Character Count: Create a dictionary (or hashmap) to store the character frequencies of string t. This will be our target frequency count.

2. Sliding Window: Use a sliding window approach. The window starts at the beginning of s.

3. Window Character Count: Maintain a second dictionary to track the character frequencies within the current window.

4. Window Expansion and Contraction:

   • Expand: Move the right pointer of the window to the right, adding characters to the window and updating the window's character frequency count.
   • Contract: If the window contains all the characters from t (i.e., the window frequency count matches the target frequency count), try to shrink the window from the left. Continue shrinking as long as the window still contains all characters from t. Update the minimum window if a smaller window is found.

5. Result: After traversing the entire string s, return the minimum window found.

Explanation

The algorithm uses a sliding window technique to efficiently find the minimum window. By keeping track of character frequencies in the window and comparing them to the target frequencies, we can efficiently determine when the window contains all required characters. The contraction step ensures we find the smallest possible window. The dictionaries allow for O(1) time complexity for character frequency lookups.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t) || s.Length < t.Length) return "";

        Dictionary<char, int> targetFreq = new Dictionary<char, int>();
        foreach (char c in t) {
            targetFreq[c] = targetFreq.GetValueOrDefault(c, 0) + 1;
        }

        Dictionary<char, int> windowFreq = new Dictionary<char, int>();
        int required = targetFreq.Count;
        int formed = 0;

        int left = 0, right = 0;
        int minWindowLength = int.MaxValue;
        int minWindowStart = 0;


        while (right < s.Length) {
            char c = s[right];
            windowFreq[c] = windowFreq.GetValueOrDefault(c, 0) + 1;

            if (targetFreq.ContainsKey(c) && windowFreq[c] == targetFreq[c]) {
                formed++;
            }

            while (left <= right && formed == required) {
                int windowLength = right - left + 1;
                if (windowLength < minWindowLength) {
                    minWindowLength = windowLength;
                    minWindowStart = left;
                }

                char leftChar = s[left];
                windowFreq[leftChar]--;
                if (targetFreq.ContainsKey(leftChar) && windowFreq[leftChar] < targetFreq[leftChar]) {
                    formed--;
                }
                left++;
            }
            right++;
        }

        return minWindowLength == int.MaxValue ? "" : s.Substring(minWindowStart, minWindowLength);
    }
}

Complexity

• Time Complexity: O(N), where N is the length of string s. The sliding window traverses the string at most twice.
• Space Complexity: O(M + N), where M is the length of string t and N is the length of the string s. This is due to the dictionaries used to store character frequencies. In the worst case, all characters in s are unique. The space required is proportional to the size of t for the targetFreq dictionary and proportional to the size of the s for the windowFreq dictionary in the worst case. However, because the windowFreq is always a subset of the characters in s, the space complexity is still upper bounded by O(M+N) where M is the size of t and N is the size of s