Minimum Window Substring

Find the smallest substring of s that contains every character of t, including duplicate counts.

Open concept page Back to problem map

This is the flagship variable-size window problem for coverage constraints.

It teaches how to track both required counts and how many requirements are currently satisfied.

Problem intuition

The brute-force version tries every possible substring and checks whether it covers the target counts.

The optimal solution grows the window until all requirements are met, then shrinks from the left to make the valid window as small as possible.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Check every substring

O(n^3)O(charset)

Generate every substring and test whether it covers all required characters. Straightforward, but very expensive.

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

class Solution {
    public String minWindow(String s, String t) {
        String best = "";

        for (int start = 0; start < s.length(); start++) {
            for (int end = start; end < s.length(); end++) {
                String candidate = s.substring(start, end + 1);
                if (covers(candidate, t)) {
                    if (best.isEmpty() || candidate.length() < best.length()) {
                        best = candidate;
                    }
                }
            }
        }

        return best;
    }

    private boolean covers(String candidate, String t) {
        Map<Character, Integer> need = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        }

        for (int i = 0; i < candidate.length(); i++) {
            char ch = candidate.charAt(i);
            if (need.containsKey(ch)) {
                need.put(ch, need.get(ch) - 1);
            }
        }

        for (int count : need.values()) {
            if (count > 0) {
                return false;
            }
        }

        return true;
    }
}

Solution 2

Sliding window with satisfied requirements

O(n)O(charset)

Track target frequencies, expand until the window is valid, then shrink greedily to capture the smallest valid answer.

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

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

        Map<Character, Integer> need = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        }

        Map<Character, Integer> window = new HashMap<>();
        int formed = 0;
        int required = need.size();
        int left = 0;
        int bestLength = Integer.MAX_VALUE;
        int bestStart = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            window.put(ch, window.getOrDefault(ch, 0) + 1);

            if (need.containsKey(ch) && window.get(ch).intValue() == need.get(ch).intValue()) {
                formed++;
            }

            while (formed == required) {
                if (right - left + 1 < bestLength) {
                    bestLength = right - left + 1;
                    bestStart = left;
                }

                char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);

                if (need.containsKey(leftChar)
                        && window.get(leftChar).intValue() < need.get(leftChar).intValue()) {
                    formed--;
                }

                left++;
            }
        }

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