← Back to Index

🔍 Minimum Window Substring – Java Cheat Sheet (One Page)

📌 What Is It?

The Minimum Window Substring problem involves finding the smallest substring in a string `s` that contains all characters of another string `t`.

• Uses the Sliding Window technique
• Requires maintaining a frequency map of characters
• Expands and shrinks the window dynamically

🧱 Pattern Template

public String minWindow(String s, String t) {
    int[] smap = new int[128];
    int[] tmap = new int[128];
    int required = 0;

    for (char c : t.toCharArray()) {
        tmap[c]++;
        if (tmap[c] == 1) required++;
    }

    int left = 0, right = 0, matched = 0;
    int minLen = Integer.MAX_VALUE;
    int minStart = 0;

    while (right < s.length()) {
        char c = s.charAt(right);
        smap[c]++;
        if (tmap[c] > 0 && smap[c] == tmap[c]) matched++;

        while (matched == required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            char lc = s.charAt(left);
            smap[lc]--;
            if (tmap[lc] > 0 && smap[lc] < tmap[lc]) matched--;
            left++;
        }
        right++;
    }

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

✅ Use Cases

• Finding substrings with specific constraints
• Text search problems
• Dynamic window size problems

📘 Common LeetCode Problems

• 76: Minimum Window Substring [Hard] Sliding Window, HashMap
• 30: Substring with Concatenation of All Words [Hard] Sliding Window, HashMap

🧪 Example: Minimum Window Substring

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

▶️ View Animation

💡 Pro Tips

• Use a frequency map to track required characters
• Expand the window to include characters, shrink to meet constraints
• Edge cases: empty strings, no valid window