LeetCode 76. Minimum Window Substring

Description

https://leetcode.com/problems/minimum-window-substring/

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

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.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Explanation

Use two pointers sliding window. Increase the right pointer to meet the target string, and adjust the left pointer to see where is the place to have a minimum substring to have the target string.

Python Solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:

        counter_t = {}
        counter_s = {}
                
        for c in t:
            counter_t[c] = counter_t.get(c, 0) + 1
            

        i = 0
        j = 0
        
        left = -1
        right = -1
        
        valid = 0
        
        for i in range(len(s)):
            
            while j < len(s) and valid < len(counter_t):
                counter_s[s[j]] = counter_s.get(s[j], 0) + 1
                
                if s[j] in counter_t and counter_s[s[j]] == counter_t[s[j]]:                    
                    valid += 1
            
                
                j += 1
                
            
            if valid == len(counter_t):
                if left == -1 or j - i < right - left:
                    left = i
                    right = j
        
            
            counter_s[s[i]] -= 1
            if s[i] in counter_t and counter_s[s[i]] == counter_t[s[i]] - 1:
                valid -= 1
                
        if left == -1:
            return ""
        
                
        return s[left : right]