leetcode-study

76. Minimum Window Substring

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
        Finds the minimum window substring in 's' that contains all characters from 't' (including duplicates).
        
        Parameters:
            s (str): The string to search within.
            t (str): The target string containing characters to include in the window.
        
        Returns:
            str: The smallest substring of 's' that contains every character in 't', or an empty string
                 if no such substring exists.
        """
        # Dictionary to count frequency of characters in t.
        dict_t = Counter(t)
        # Total unique characters in t that need to be present in the window.
        required = len(dict_t)
        
        # Left and right pointers for the sliding window.
        l, r = 0, 0
        # Tracks the number of unique characters in the current window that match the required frequency.
        formed = 0
        # Dictionary to keep track of all characters in the current window.
        window_counts = {}
        
        # Tuple (window length, left, right) to hold the best (smallest) window seen so far.
        ans = float("inf"), None, None
        
        # Expand the window by moving the right pointer.
        while r < len(s):
            character = s[r]
            # Add current character to the window count.
            window_counts[character] = window_counts.get(character, 0) + 1
            
            # If current character's frequency matches its required count in t, increase 'formed'.
            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1
            
            # Contract the window from the left if all required characters are present.
            while l <= r and formed == required:
                character = s[l]
                
                # Update the answer if this window is smaller than previously recorded ones.
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)
                
                # Remove the character at the left pointer from the window count.
                window_counts[character] -= 1
                # If the removed character's count drops below its required frequency, reduce 'formed'.
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1
                
                # Move the left pointer ahead to try and find a smaller valid window.
                l += 1
            
            # Expand the window by moving the right pointer.
            r += 1
        
        # Return the smallest window if found; otherwise, return an empty string.
        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]

Summary of Techniques and Approaches:

• Sliding Window Technique: The solution dynamically adjusts the window boundaries with two pointers (left and right) to identify valid substrings efficiently.

• Two-Pointer Strategy: By expanding the window with the right pointer and contracting it with the left pointer once requirements are met, the method minimizes unnecessary iterations for optimal performance.

• Hash Map for Frequency Counting: Using a dictionary (or Counter) to record the frequency of characters enables constant-time checks on whether the current window satisfies the frequency requirements of t.

• Incremental Validation: The variable formed is used to keep track of when the current window meets all necessary conditions, reducing redundant checks and ensuring only valid windows are considered for minimization.

• General Applicability: These techniques can be applied to other problems involving dynamic window resizing, such as substring search, array partitioning, or pattern matching challenges. Identify when a problem asks for finding the smallest/largest subarray or substring with specific properties, and consider leveraging the sliding window approach for an efficient and elegant solution.