LeetCode 76 - Minimum Window Substring

Link : https://leetcode.com/problems/minimum-window-substring

Problem Description

Given two strings s and t, return the minimum window substring of s that contains all characters in t. If no such substring exists, return an empty string.

Solution Approach

We use the sliding window technique with two pointers to find the minimum window. The solution maintains a frequency map of required characters and dynamically adjusts the window size.

Time Complexity: O(n)

• Single pass through string s with two pointers
• Each character is processed at most twice (once by end pointer, once by start pointer)

Space Complexity: O(1)

• Fixed size array of 128 characters (ASCII)
• Space doesn't grow with input size

Visual Explanation

Let's take the example: s = "ADOBECODEBANC", t = "ABC"

Initial state:

A D O B E C O D E B A N C
↑
start,end

Moving end pointer until we have all required characters:

A D O B E C O D E B A N C
↑         ↑
start     end
[Found: A,B,C]

Trying to minimize by moving start:

A D O B E C O D E B A N C
    ↑     ↑
    start end
[Window invalid, missing A]

Continue moving end:

A D O B E C O D E B A N C
    ↑               ↑
    start           end
[Found: A,B,C in "BECODEBA"]

Minimize again:

A D O B E C O D E B A N C
                ↑   ↑
                s   e
[Found minimum: "BANC"]

Key Implementation Details

1. Frequency Map

   For t = "ABC":
   targetFreq['A'] = 1
   targetFreq['B'] = 1
   targetFreq['C'] = 1
   All others = 0
   

2. Window Management

   • Expand window when missing characters (move end pointer)
   • Contract window when all characters found (move start pointer)
   • Track minimum window size and starting position

3. Required Counter

   • Decrements when we find a needed character
   • Increments when we remove a needed character
   • Window is valid when counter = 0

Edge Cases

1. Empty strings → return ""
2. Null inputs → return ""
3. t longer than s → return ""
4. Single character match → return that character
5. No possible window → return ""

Example Test Cases

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

Input: s = "a", t = "a"
Output: "a"

Input: s = "a", t = "aa"
Output: ""

Code

/**
 * Solution for LeetCode 76: Minimum Window Substring
 * Uses sliding window technique to find the smallest substring containing all characters from target string
 */
class MinimumWindowSubstring {
    /**
     * Finds the minimum window substring containing all characters from string t in string s
     * @param s Source string to search in
     * @param t Target string containing characters to find
     * @return Smallest substring of s containing all characters of t
     */
    public String minWindow(String s, String t) {
        // Handle edge cases: null inputs, empty strings, or t longer than s
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }

        // Create frequency map for characters in t using ASCII values (0-127)
        // targetFreq[i] represents how many times we need character with ASCII value i
        int[] targetFreq = new int[128];
        for (char c : t.toCharArray()) {
            targetFreq[c]++;
        }

        // Initialize window pointers and tracking variables
        int start = 0;          // Left pointer of sliding window
        int minStart = 0;       // Start index of minimum window found so far
        int minLen = Integer.MAX_VALUE;  // Length of minimum window found so far
        int required = t.length();       // Number of characters still needed to form valid window

        // Iterate through string s with right pointer (end)
        for (int end = 0; end < s.length(); end++) {
            // If current character is needed (frequency > 0), decrease required count
            if (targetFreq[s.charAt(end)]-- > 0) {
                required--;
            }

            // When we have all required characters (valid window found)
            while (required == 0) {
                // Update minimum window if current window is smaller
                if (end - start + 1 < minLen) {
                    minStart = start;
                    minLen = end - start + 1;
                }

                // Try to minimize window by moving start pointer
                // If removing the start character makes window invalid (frequency becomes positive)
                // increment required count
                if (++targetFreq[s.charAt(start)] > 0) {
                    required++;
                }
                start++;
            }
        }

        // Return minimum window substring or empty string if none found
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }

    // Test cases
    public static void main(String[] args) {
        MinimumWindowSubstring solution = new MinimumWindowSubstring();

        // Test case 1: Normal case with multiple occurrences
        String s1 = "ADOBECODEBANC";
        String t1 = "ABC";
        System.out.println("Test 1: " + solution.minWindow(s1, t1));  // Expected: "BANC"

        // Test case 2: Single character match
        String s2 = "a";
        String t2 = "a";
        System.out.println("Test 2: " + solution.minWindow(s2, t2));  // Expected: "a"

        // Test case 3: Impossible case (not enough characters)
        String s3 = "a";
        String t3 = "aa";
        System.out.println("Test 3: " + solution.minWindow(s3, t3));  // Expected: ""
    }
}