76. Minimum Window Substring

Problem Link

We need to find the minimum length substring in \(s\), such that all characters from \(t\) is present in the substring. To solve it we can use a sliding window (\(l\), \(r\) bounds), in which a valid window would indicate a substring with all characters in \(t\). To do this,

• we can maintain a variable \(missing = length(t)\) which would indicate the number of missing character from \(t\) in current window.
• To make sure that \(missing\) is only updated for needed character, we'll use a hashmap (\(need\)) which indicates the frequency of consumed characters in our window and populate it with counts from \(t\).

With this setup, when we shift our window to right:

1. Check if the current character is needed using hashmap, if so we can decrement it from \(missing\).
2. Then we decrement the count of current character regardless, since this step would simplify the code for shrinking the window to correct position.
3. When our \(missing\) variable reaches \(0\), it means we've found all the characters from \(t\) in our window \((l, r)\).
   • Since we've been ignoring the start of window, we've to fix it to correct position. This is now simple because we're maintaining \(need\) hashmap which would've negative frequency for overconsumed characters and \(0\) count for needed characters. This approach also handles few subtleties like for example, \(window = BCBA\) and \(t = ABC\), here we'll safely ignore the first \(B\) as its already account for in smaller \(window=CBA\).
   • Now the start of window is appropriate, we can check it against the optimal result and update.
   • Since we've consumed this window, we'll shrink the window from left to move forward.

Runtime Complexity

Time: \(O(n)\) as each character is only processed once.

Space: \(O(1)\) from hashmap storing only english character keys

PythonGo

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        missing = len(t)
        l = R = L = 0
        for r, ch in enumerate(s, 1):
            if need[ch] > 0:
                missing -= 1
            need[ch]-=1
            if missing == 0:
                while l < r and need[s[l]] < 0:
                    need[s[l]]+=1
                    l+=1
                if R == 0 or r-l < R-L:
                    R, L = r, l
                need[s[l]] += 1
                missing += 1
                l += 1
        return s[L:R]

func minWindow(s string, t string) string {
    needs := make(map[rune]int)
    for _, ch := range t {
        needs[ch]++
    }
    missing := len(t)
    var l, R, L int
    for r, ch := range s {
        if val, _ := needs[ch]; val > 0 {
            missing--
        }
        needs[ch]--
        if missing == 0 {
            for l <= r && needs[rune(s[l])] < 0 {
                needs[rune(s[l])]++
                l++
            }
            if (R == 0) || (r-l < R-L) {
                R, L = r+1, l
            }
            needs[rune(s[l])]++
            missing++
            l++
        }
    }
    return s[L:R]
}

---