Minimum Window Substring hard

Problem Statement

Given two strings s and t, find the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "". If there are multiple minimum-window substrings, you can return any one of them.

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.

Steps:

1. Character Count: Create a map (HashMap in Java) to store the character frequencies of string t. This map will track how many occurrences of each character we need to find in s.

2. Sliding Window: Use a sliding window approach. Maintain two pointers, left and right, representing the start and end of the window in s.

3. Window Expansion: Expand the window by moving the right pointer. For each character added to the window, update a required counter which tracks the number of characters from t that are still needed in the window.

4. Window Contraction: If required becomes 0 (meaning we've found all characters from t within the window), try to contract the window by moving the left pointer. This helps find the minimum window. While contracting, if a character is removed that's in t, update required accordingly.

5. Minimum Window Tracking: Keep track of the minimum window found so far.

6. Return Result: After iterating through the entire string s, return the minimum window found. If no such window exists, return an empty string.

Explanation:

The solution leverages the sliding window technique for efficiency. Instead of checking all possible substrings, it intelligently expands and contracts a window to find the minimum substring containing all characters from t. The required counter helps determine when the window contains all necessary characters, and the character frequency map ensures we are accurately tracking character counts within the window. The process of contracting the window from the left minimizes the substring length while ensuring all required characters are still present.

Code:

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

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

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

        int required = charCount.size(); // Number of unique characters in t
        int formed = 0; // Number of unique characters in t that are present in the window

        int left = 0, right = 0;
        Map<Character, Integer> windowCount = new HashMap<>();
        int[] ans = {-1, 0, 0}; // [length, left, right]

        while (right < s.length()) {
            char c = s.charAt(right);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);

            if (charCount.containsKey(c) && windowCount.get(c).intValue() == charCount.get(c).intValue()) {
                formed++;
            }

            while (left <= right && formed == required) {
                c = s.charAt(left);
                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }

                windowCount.put(c, windowCount.get(c) - 1);
                if (charCount.containsKey(c) && windowCount.get(c) < charCount.get(c)) {
                    formed--;
                }
                left++;
            }
            right++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

Complexity:

• Time Complexity: O(M + N), where N is the length of s and M is the length of t. The sliding window traverses the string s once.

• Space Complexity: O(M), in the worst case, to store the character frequencies of t in the HashMap. The space used for the sliding window is also proportional to M.