Minimum Window Substring

Master this topic with zero to advance depth.

Minimum Window Substring

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

Visual Representation

s = "ADOBECODEBANC", t = "ABC"

Window Expand (Found all ABC):
[ADOBEC]ODEBANC   (Len: 6)

Window Shrink (Still have ABC):
 A [DOBEC]ODEBANC (Len: 5) -> [DOBEC] (Wait, missing A!)

Final Optimal Window:
ADOBECODE [BANC] (Len: 4)

Hard

Examples

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Approach 1

Level I: Brute Force

Intuition

Check every possible substring of s and verify if it contains all characters of t in the required frequencies. Keep track of the minimum length substring that satisfies this.

Thought Process

Iterate through all possible start and end indices to define every substring.
For each substring, count its character frequencies.
Compare these frequencies with the target frequency map of t.
If the substring is valid, update the minWindow result.

⏱ O(N^2 * M) where N is length of s and M is length of t.💾 O(N + M)

Detailed Dry Run

Substring	Valid?	Min Length	Min Window
"ADOBE"	No (missing C)	inf	""
"ADOBEC"	YES!	6	"ADOBEC"
"BANC"	YES!	4	"BANC"

java

import java.util.*;

public class Main {
    public static String minWindow(String s, String t) {
        String result = "";
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (isValid(sub, t)) {
                    if (sub.length() < minLen) {
                        minLen = sub.length();
                        result = sub;
                    }
                }
            }
        }
        return result;
    }

    private static boolean isValid(String sub, String t) {
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        Map<Character, Integer> subMap = new HashMap<>();
        for (char c : sub.toCharArray()) subMap.put(c, subMap.getOrDefault(c, 0) + 1);
        for (char c : tMap.keySet()) {
            if (subMap.getOrDefault(c, 0) < tMap.get(c)) return false;
        }
        return true;
    }

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

Approach 2

Level II: Binary Search on Window Size

Intuition

The shortest valid window length must be between len(t) and len(s). We can binary search for this length k. For each k, we use a fixed-size sliding window of length k to check if any valid substring exists. If it does, we try smaller lengths; otherwise, we try larger ones.

⏱ O(N log N) where N is the length of s.💾 O(K) where K is the number of unique characters.

Detailed Dry Run

Input: s = "ADOBECODEBANC", t = "ABC"

Binary Search range: [3, 13].
Try k = 8: Substring ADOBECOD is valid. Search [3, 7].
Try k = 5: Substring EBANC is valid. Search [3, 4].
Try k = 4: Substring BANC is valid. Search [3, 3].
Try k = 3: No window of size 3 is valid.
Result: k = 4, return BANC.

java

import java.util.*;

public class Solution {
    public String minWindow(String s, String t) {
        int left = t.length(), right = s.length();
        String result = "";
        Map<Character, Integer> target = new HashMap<>();
        for (char c : t.toCharArray()) target.put(c, target.getOrDefault(c, 0) + 1);

        while (left <= right) {
            int mid = left + (right - left) / 2;
            String current = check(s, t, mid, target);
            if (!current.isEmpty()) {
                result = current;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    private String check(String s, String t, int k, Map<Character, Integer> target) {
        Map<Character, Integer> window = new HashMap<>();
        int formed = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (target.containsKey(c) && window.get(c).equals(target.get(c))) formed++;
            if (i >= k) {
                char out = s.charAt(i - k);
                if (target.containsKey(out) && window.get(out).equals(target.get(out))) formed--;
                window.put(out, window.get(out) - 1);
            }
            if (formed == target.size()) return s.substring(i - k + 1, i + 1);
        }
        return "";
    }
}

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Categorization

This is a Variable Size Window problem. We need to find the smallest range [L, R] that satisfies the requirement.

Thought Process

Use a map targetCounts to store required characters in t.
Expand right until the window contains all characters in t. We use a have counter vs a need counter for $O(1)$ validity check.
Once valid, shrink left as much as possible while maintaining validity to find the smallest window.
Update the minWindow result whenever a smaller valid window is found.

Mandatory Variables

left, right: Window pointers.
targetMap: Frequencies of characters in t.
windowMap: Frequencies of characters in the current window.
have, need: Variables to track progress toward the target frequency.

⏱ O(N + M) where N is length of s and M is length of t.💾 O(M) for frequency maps.

Detailed Dry Run

s = "ADOBEC", t = "ABC"

Step	L	R	Char	Window Map	Have/Need	Action
1	0	0	'A'	{A:1}	1/3	Expand
2-4	0	4	'E'	{A:1, B:1}	2/3	Expand
5	0	5	'C'	{A:1, B:1, C:1}	3/3	VALID!
6	1	5	'D'	{B:1, C:1}	2/3	Shrink (Invalidated)

java

import java.util.*;

public class Main {
    public static String minWindow(String s, String t) {
        if (t.isEmpty()) return "";
        Map<Character, Integer> countT = new HashMap<>(), window = new HashMap<>();
        for (char c : t.toCharArray()) countT.put(c, countT.getOrDefault(c, 0) + 1);

        int have = 0, need = countT.size();
        int[] res = {-1, -1}; int resLen = Integer.MAX_VALUE;
        int L = 0;

        for (int R = 0; R < s.length(); R++) {
            char c = s.charAt(R);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (countT.containsKey(c) && window.get(c).equals(countT.get(c))) have++;

            while (have == need) {
                if ((R - L + 1) < resLen) {
                    resLen = R - L + 1;
                    res[0] = L; res[1] = R;
                }
                char leftChar = s.charAt(L);
                window.put(leftChar, window.get(leftChar) - 1);
                if (countT.containsKey(leftChar) && window.get(leftChar) < countT.get(leftChar)) have--;
                L++;
            }
        }
        return resLen == Integer.MAX_VALUE ? "" : s.substring(res[0], res[1] + 1);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with character counts if t has duplicates. Using a have/need counter for unique characters is more robust than a total character count.

← Previous QuestionPermutation in String

Next Question →Max Consecutive Ones III

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.