76. Minimum Window Substring

Problem Statement

link: LeetCode.cn LeetCode 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.

Example:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC"

Input: s = "a", t = "a" Output: "a"

Input: s = "a", t = "aa" Output: ""

Solution Approach

Use a sliding window and character count arrays to find the smallest substring in s that contains all characters of t.

Algorithm

1. Character Mapping: Utilize two count arrays, one for the characters in the target string t and another for the characters in the current window of the source string s, ensuring that both uppercase and lowercase letters are accurately mapped.
2. Sliding Window: Expand the right pointer r to include characters from s into the window and contract the left pointer l to find the smallest possible window that still contains all characters from t.
3. Window Validation: Implement a helper function to check if the current window meets the requirements by comparing the count arrays, and update the minimum window size and starting position when a valid window is found.

Implement

    class Solution: def minWindow(self, s: str, t: str) -> str:
    if len(s) < len(t) or not s or not t:
        return ""
    
    def f(chr):
        if 'a' <= chr <= 'z':
            return ord(chr) - ord('a') + 26
        else:
            return ord(chr) - ord('A')
    
    ct_t = [0] * 52
    for c in t:
        ct_t[f(c)] += 1
    
    l, r, n = 0, 0, len(s)
    ct = [0] * 52
    mini_l = float('inf')
    start = 0
    
    def contains_all(ct, ct_t):
        for i in range(52):
            if ct_t[i] > ct[i]:
                return False
        return True
    
    while r < n:
        ct[f(s[r])] += 1

        while contains_all(ct, ct_t):  # Here it must be contains rather than equals relationship
            if r - l + 1 < mini_l:  # Here it must update simultaneously
                mini_l = r - l + 1
                start = l
            ct[f(s[l])] -= 1
            l += 1

        r += 1
    
    return s[start:start + mini_l] if mini_l != float('inf') else ""

    
    

Twitter  facebook  Email