Given two strings s and t of lengths m and n respectively, return the minimum window

 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?. Implement with java. Insert comments in the code

Answer:

Here is the Java implementation of the minimum window substring problem that runs in O(m + n) time complexity:

java
import java.util.*;

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        
        // create a hash map to store the characters and their frequencies in t
        Map<Character, Integer> target = new HashMap<>();
        for (char c : t.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }
        
        // create variables to keep track of the minimum window substring
        int left = 0;
        int right = 0;
        int count = target.size();
        int minLength = Integer.MAX_VALUE;
        String result = "";
        
        // iterate through s and find the minimum window substring
        while (right < s.length()) {
            char c = s.charAt(right);
            if (target.containsKey(c)) {
                target.put(c, target.get(c) - 1);
                if (target.get(c) == 0) {
                    count--;
                }
            }
            right++;
            
            while (count == 0) {
                if (right - left < minLength) {
                    minLength = right - left;
                    result = s.substring(left, right);
                }
                char c2 = s.charAt(left);
                if (target.containsKey(c2)) {
                    target.put(c2, target.get(c2) + 1);
                    if (target.get(c2) > 0) {
                        count++;
                    }
                }
                left++;
            }
        }
        
        return result;
    }
}

The algorithm works as follows:

1. Create a hash map to store the characters and their frequencies in t.
2. Create variables to keep track of the minimum window substring, including its starting and ending indices, its length, and the characters and their frequencies that still need to be included in the window.
3. Iterate through s using two pointers, left and right, to find the minimum window substring:
   • If the current character is in t, decrement its frequency in the hash map and update the count of remaining characters to be included in the window.
   • If the count is 0, we have found a valid window. Update the minimum length and result accordingly.
   • Increment the left pointer and update the hash map and count as necessary.
4. Return the minimum window substring.

The time complexity of this algorithm is O(m + n), where m is the length of s and n is the length of t, since we iterate through s and t once each, and the hash map operations are constant time.