Minimum Window Substring - Java Solution

1. Introduction

This blog post is dedicated to solving the "Minimum Window Substring" problem, a challenging task involving string manipulation and the sliding window technique. It focuses on finding the smallest substring in 's' that contains all the characters (including duplicates) of another string 't'.

Problem

Given two strings 's' and 't', the objective is to find the minimum window in 's' which will contain all the characters in 't'. If no such substring exists, the function should return an empty string. The problem guarantees that the answer is unique if it exists.

2. Solution Steps

1. Create hashmaps to store the frequency of characters in 't' and in the current window of 's'.

2. Use two pointers to define the sliding window's boundaries in 's'.

3. Expand the right boundary of the window to include characters until all characters in 't' are covered.

4. Contract the window from the left to find the smallest possible window that still covers all characters in 't'.

5. Update the minimum window size and its starting index during the contraction phase.

6. Return the minimum window substring found.

3. Code Program

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

public class MinimumWindowSubstring {
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // Example 1
        System.out.println(minWindow("a", "a"));              // Example 2
        System.out.println(minWindow("a", "aa"));             // Example 3
    }

    // Function to find the minimum window substring
    public static String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";

        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> windowMap = new HashMap<>();
        int start = 0, minLen = Integer.MAX_VALUE, minStart = 0;
        int count = 0;

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

            if (tMap.containsKey(c) && windowMap.get(c).intValue() == tMap.get(c).intValue()) {
                count++;
            }

            while (count == tMap.size()) {
                if (end - start + 1 < minLen) {
                    minLen = end - start + 1;
                    minStart = start;
                }

                char startChar = s.charAt(start++);
                windowMap.put(startChar, windowMap.get(startChar) - 1);

                if (tMap.containsKey(startChar) && windowMap.get(startChar) < tMap.get(startChar)) {
                    count--;
                }
            }
        }

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

Output:

"BANC"
"a"
""

Explanation:

1. minWindow: The function uses a sliding window approach to find the smallest substring in 's' that contains all characters in 't'.

2. Two hashmaps are used to track the frequency of characters in 't' and in the current window of 's'.

3. The right boundary of the window is expanded to include characters from 's' until all characters in 't' are covered.

4. Once all characters are covered, the window is contracted from the left to minimize its size while still covering all characters in 't'.

5. During contraction, the function keeps track of the minimum window size and its starting index.

6. The function returns the substring of 's' that represents the minimum window containing all characters in 't'. If no such window exists, it returns an empty string.