LeetCode Hard – 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.

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?

Java Solution

You can solve this problem using the sliding window technique. Here’s a Java solution that runs in O(m + n) time:

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }

        Map<Character, Integer> targetFreq = new HashMap<>();
        for (char ch : t.toCharArray()) {
            targetFreq.put(ch, targetFreq.getOrDefault(ch, 0) + 1);
        }

        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
        int requiredChars = t.length();

        while (right < s.length()) {
            char currentChar = s.charAt(right);
            if (targetFreq.containsKey(currentChar)) {
                if (targetFreq.get(currentChar) > 0) {
                    requiredChars--;
                }
                targetFreq.put(currentChar, targetFreq.get(currentChar) - 1);
            }

            while (requiredChars == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    minLeft = left;
                }

                char leftChar = s.charAt(left);
                if (targetFreq.containsKey(leftChar)) {
                    targetFreq.put(leftChar, targetFreq.get(leftChar) + 1);
                    if (targetFreq.get(leftChar) > 0) {
                        requiredChars++;
                    }
                }

                left++;
            }

            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen + 1);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));  // Output: "BANC"
        System.out.println(minWindow("a", "a"));                // Output: "a"
        System.out.println(minWindow("a", "aa"));               // Output: ""
    }
}

This Java code uses two pointers, left and right, to form a sliding window. The targetFreq map is used to keep track of the characters and their frequencies in string t. The algorithm moves the window to find the minimum window substring that contains all characters from t. The minLen and minLeft variables store the minimum length and starting index of the window, respectively. The while loop adjusts the window based on the current state of characters in the window and the required characters from t. The result is then obtained using substring operations.

Python Solution

from collections import Counter

def min_window(s, t):
    if not s or not t:
        return ""

    target_freq = Counter(t)
    required_chars = len(t)
    left = right = 0
    min_len = float('inf')
    min_left = 0

    while right < len(s):
        current_char = s[right]
        if current_char in target_freq:
            if target_freq[current_char] > 0:
                required_chars -= 1
            target_freq[current_char] -= 1

        while required_chars == 0:
            if right - left < min_len:
                min_len = right - left
                min_left = left

            left_char = s[left]
            if left_char in target_freq:
                target_freq[left_char] += 1
                if target_freq[left_char] > 0:
                    required_chars += 1

            left += 1

        right += 1

    return "" if min_len == float('inf') else s[min_left:min_left + min_len + 1]

# Test cases
print(min_window("ADOBECODEBANC", "ABC"))  # Output: "BANC"
print(min_window("a", "a"))                # Output: "a"
print(min_window("a", "aa"))               # Output: ""

This Python code follows the same sliding window approach. It uses the Counter class from the collections module to keep track of character frequencies. The algorithm iterates through the string s and adjusts the window based on the current state of characters in the window and the required characters from t. The result is then obtained using substring operations.