minWindow

import java.util.HashMap;

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

        // Step 1: Count of required characters from t
        HashMap<Character, Integer> requiredCount = new HashMap<>();
        for (char ch : t.toCharArray()) {
            requiredCount.put(ch, requiredCount.getOrDefault(ch, 0) + 1);
        }

        // Window map to keep track of current window counts
        HashMap<Character, Integer> windowCount = new HashMap<>();

        // Pointers for sliding window
        int leftPointer = 0;
        int rightPointer = 0;

        // To check how many unique characters are satisfied
        int satisfiedChars = 0;
        int totalRequiredUniqueChars = requiredCount.size();

        // To track the minimum window
        int bestWindowLength = Integer.MAX_VALUE;
        int bestWindowStart = 0;

        // Expand the window with rightPointer
        while (rightPointer < s.length()) {
            char currentChar = s.charAt(rightPointer);
            windowCount.put(currentChar, windowCount.getOrDefault(currentChar, 0) + 1);

            // If currentChar count matches exactly what we need, increase satisfied count
            if (requiredCount.containsKey(currentChar) &&
                windowCount.get(currentChar).intValue() == requiredCount.get(currentChar).intValue()) {
                satisfiedChars++;
            }

            // Shrink the window from left when all required chars are satisfied
            while (satisfiedChars == totalRequiredUniqueChars) {
                // Update best window if this one is smaller
                int currentWindowLength = rightPointer - leftPointer + 1;
                if (currentWindowLength < bestWindowLength) {
                    bestWindowLength = currentWindowLength;
                    bestWindowStart = leftPointer;
                }

                // Now try to shrink window
                char leftChar = s.charAt(leftPointer);
                windowCount.put(leftChar, windowCount.get(leftChar) - 1);

                // If we lose a required char from the window, decrease satisfiedChars
                if (requiredCount.containsKey(leftChar) &&
                    windowCount.get(leftChar) < requiredCount.get(leftChar)) {
                    satisfiedChars--;
                }

                leftPointer++; // shrink the window
            }

            // Expand window
            rightPointer++;
        }

        return bestWindowLength == Integer.MAX_VALUE 
                ? "" 
                : s.substring(bestWindowStart, bestWindowStart + bestWindowLength);
    }
}