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 is "a".

Steps

1. Create a frequency map for t: This map will store the frequency of each character in t.
2. Use a sliding window approach: We'll maintain a sliding window within s.
3. Maintain a frequency map for the window: This map will track the frequency of characters within the current window.
4. Expand the window: Move the right pointer of the window to the right, adding characters to the window and updating the window's frequency map.
5. Check if the window contains all characters from t: If the frequency of each character in the window's map is greater than or equal to its frequency in t's map, we've found a valid window.
6. Shrink the window: If a valid window is found, move the left pointer to the right, shrinking the window until it's no longer valid. Keep track of the minimum valid window found so far.
7. Repeat steps 4-6: Continue expanding and shrinking the window until the right pointer reaches the end of s.

Explanation

The sliding window technique is efficient because it avoids redundant checks. Instead of checking all possible substrings, we iteratively expand and contract a window, only updating the frequency counts of characters at the window boundaries. This significantly reduces the time complexity. The use of frequency maps allows for efficient tracking of character counts.

Code

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

    const tMap: { [key: string]: number } = {};
    for (let char of t) {
        tMap[char] = (tMap[char] || 0) + 1;
    }

    let required = Object.keys(tMap).length;
    let formed = 0;

    let left = 0, right = 0;
    let windowCounts: { [key: string]: number } = {};
    let ans = "";
    let ansLen = Infinity;

    while (right < s.length) {
        const char = s[right];
        windowCounts[char] = (windowCounts[char] || 0) + 1;

        if (tMap[char] !== undefined && windowCounts[char] === tMap[char]) {
            formed++;
        }

        while (left <= right && formed === required) {
            const windowLen = right - left + 1;
            if (windowLen < ansLen) {
                ansLen = windowLen;
                ans = s.substring(left, right + 1);
            }

            const leftChar = s[left];
            windowCounts[leftChar]--;
            if (tMap[leftChar] !== undefined && windowCounts[leftChar] < tMap[leftChar]) {
                formed--;
            }
            left++;
        }
        right++;
    }
    return ans;
}

Complexity

• Time Complexity: O(S), where S is the length of string s. We iterate through s at most twice (once for expanding the window and once for shrinking it).
• Space Complexity: O(m + n), where m is the size of the character set (e.g., 26 for lowercase English letters) and n is the length of string t. This is due to the frequency maps we use. In the worst case, m is dominated by the length of s itself.