The O(n) Club: Minimum Window Substring—How to Find a Needle in a Haystack Without Setting the Hay on Fire

The O(n) Club: Minimum Window Substring—How to Find a Needle in a Haystack Without Setting the Hay on Fire

⚡ TL;DR

Squeeze every character from t (with duplicate drama!) into the smallest possible chunk of s. Brute force? O(n²) regret. Sliding window + hashmaps = your new best friends in Java.

Java brute force, for anyone who wants to feel pain:

for (int i = 0; i < s.length(); i++) {
    for (int j = i + 1; j <= s.length(); j++) {
        String sub = s.substring(i, j);
        // Check if 'sub' has all of t, counts included (enjoy).
    }
}

🧠 How Devs Usually Mess This Up

Step 1: Only count if one of each letter in t is in your window. Congratulate yourself for finding ‘ABC’ in ‘AABBC’. Step 2: Realize too late that if t = "AAB", you just returned one A too few, and the interviewer sighs loudly.

Special shoutout to folks who shrink the window before double-checking all char counts: enjoy your off-by-one adventure. And please, don’t confuse “contains all” with “is the same as”—t might have more drama than your substring expects.

🔍 What’s Actually Going On

Imagine a robot vacuum, but instead of crumbs, it collects every instance of each letter from t. It expands its sweep until everything’s collected (even those sneaky duplicates), then tries to contract—without letting a single crumb escape. Hashmaps are its memory, keeping track of what it still needs. This robot only knows how to move forward, which is why it’s O(n) and not stuck cleaning a loop all day.

🛠️ PseudoCode

• Build a need map:
  Map<Character, Integer> need = new HashMap<>(); // Count what you want from t
• Two pointers: left = 0; right = 0 // Your window boundaries
• Another hashmap for window: windowCounts // Track what’s in the window
• Expand right: Increase window until all chars in need are met
• Shrink left: Move left as long as the window is valid (don’t drop below what’s needed)
• Track smallest window length and index
• Return min window substring (or the world’s emptiest string if not found)

💻 The Code

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) return "";
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray())
        need.put(c, need.getOrDefault(c, 0) + 1);
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0, formed = 0, required = need.size();
    int minLen = Integer.MAX_VALUE, minLeft = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) formed++;
        while (left <= right && formed == required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }
            char lc = s.charAt(left);
            window.put(lc, window.get(lc) - 1);
            if (need.containsKey(lc) && window.get(lc) < need.get(lc)) formed--;
            left++;
        }
        right++;
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicates matter: No cheating—if t = "AABC", having just one A is a fail.
• Case-sensitivity apocalypse: 'a' is not 'A'. Not even in Java’s dreams.
• No possible substring: t has a char that s doesn’t? Say hello to “” (and awkward silence in your code review).
• Performance: O(n) clean—each pointer only goes forward. Your CPU can drink its coffee in peace.

🧠 Interviewer Brain-Tattoo

“Always ask: Am I meeting everyone’s needs, or just giving empty promises? (Your code AND your dating life.)”