LeetCode: 76 Minimum Window Substring

Problem Description:

Given two strings s and t, 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 "".

Example 1:

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

Example 2:

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

Example 3:

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

Original Code with Comments:

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l = 0  # Initialize left pointer for the sliding window
        t_map, window = {}, {}  # Create frequency maps for t and the current window

        # Populate the frequency map for characters in t
        for c in t:
            t_map[c] = t_map.get(c, 0) + 1  # Count occurrences of each character in t

        have, need = 0, len(t_map)  # 'have' tracks matched characters, 'need' is the total unique characters needed
        res, res_len = [-1, -1], float("inf")  # Initialize result and minimum length

        # Expand the window by moving the right pointer
        for r in range(len(s)):
            c = s[r]  # Current character at right pointer
            window[c] = window.get(c, 0) + 1  # Update the character count in the current window

            # If the current character's frequency matches the required frequency
            if c in t_map and window[c] == t_map[c]:
                have += 1  # Increment the matched character count

            # While all required characters are matched, try to contract the window
            while have == need:
                # Check if the current window is smaller than the previous minimum
                if (r - l + 1) < res_len:
                    res = [l, r]  # Update result with the current window's indices
                    res_len = (r - l + 1)  # Update the minimum length

                window[s[l]] -= 1  # Remove the character at the left pointer from the window
                # If the frequency of the removed character is less than required, decrement 'have'
                if s[l] in t_map and window[s[l]] < t_map[s[l]]:
                    have -= 1  # Decrement the matched character count

                l += 1  # Move the left pointer to the right to contract the window

        l, r = res  # Unpack the result indices

        # Return the minimum window substring or an empty string if no valid window was found
        return s[l: r + 1] if res_len != float("inf") else ""

Explanation of the Approach:

Frequency Counting:
- Use a dictionary to count the frequency of each character in string t.
Sliding Window:
- Maintain a window defined by two pointers (l for left and r for right) to explore substrings of s.
- Expand the window by moving the right pointer and include characters in the window’s count.
- Check if the current window contains all characters from t with the required frequency.
- If the window is valid, attempt to contract it from the left to find the smallest valid window.
Updating Result:
- When a valid window is found, compare its size with the previously found minimum window and update the result if it’s smaller.

Example Execution:

Assuming we have the following input:

s = "ADOBECODEBANC"
t = "ABC"

Execution steps:

Initialization:
- t_map = {'A': 1, 'B': 1, 'C': 1}, need = 3, l = 0, have = 0, res = [-1, -1], res_len = inf.
Expand the window:
- Iterate through s:
  - r = 0: Add A → window = {'A': 1} → have = 1.
  - r = 1: Add D → window = {'A': 1, 'D': 1} → have = 1.
  - r = 2: Add O → window = {'A': 1, 'D': 1, 'O': 1} → have = 1.
  - r = 3: Add B → window = {'A': 1, 'D': 1, 'O': 1, 'B': 1} → have = 2.
  - r = 4: Add E → window = {'A': 1, 'D': 1, 'O': 1, 'B': 1, 'E': 1} → have = 2.
  - r = 5: Add C → window = {'A': 1, 'D': 1, 'O': 1, 'B': 1, 'E': 1, 'C': 1} → have = 3.
Contract the window:
- When have equals need, try to contract:
  - l = 0: Check A → Update res = [0, 5], res_len = 6 → Remove A → window = {'A': 0, 'D': 1, 'O': 1, 'B': 1, 'C': 1} → have = 2.
  - Move l = 1: Check D → Continue.
  - Move l = 2: Check O → Continue.
  - Move l = 3: Check B → Continue.
  - Move l = 4: Check E → Continue.
  - Move l = 5: Check C → Update res = [9, 12], res_len = 4 → Remove C → window = {'A': 0, 'D': 0, 'O': 1, 'B': 1} → have = 2.
Final Result:
- After iterating through s, returns the minimum window substring: "BANC".

Time Complexity Analysis:

Time Complexity: O(n)
- Where n is the length of the string s. Both pointers (l and r) traverse the string at most twice.

Space Complexity Analysis:

Space Complexity: O(1)
- The frequency dictionary size is constant since it only stores counts for 26 uppercase letters.

Tips and Warnings:

Edge Cases:
- Consider cases where s or t is empty.
Character Set Support:
- The solution assumes the character set consists of uppercase letters; adjustments are needed for other character sets.
Understanding Sliding Window:
- Ensure understanding of the sliding window logic and how to efficiently adjust the window based on conditions.

Improvement Solutions

The current implementation is efficient and meets the problem requirements. Alternative counting methods can be considered, but there is no significant efficiency improvement.

Summary

Sliding Window Method: Effectively finds the minimum window substring that contains all characters from t, with a time complexity of O(n).
Clear and Understandable: The code is straightforward and easy to understand, suitable for handling this type of problem.

Application Tips

Choose Appropriate Methods:
- Select the method best suited to specific problem requirements to ensure efficiency and readability.
Handle Edge Cases:
- Always consider edge cases in algorithm design to avoid potential errors.
Optimize Space Usage:
- When handling large datasets, consider using space-efficient algorithms.

Post Views: 33

CODEBITWAVE