Minimum Window Substring - Java Solution

1. Introduction

This post explores a solution to the "Minimum Window Substring" problem, a classic challenge in string manipulation. The objective is to find the smallest substring in a given string s that contains all the characters of another string t, including duplicates. This problem is a good test of understanding sliding window techniques in string processing.

Problem

Given two strings s and t, where s is the main string and t is the target string, the task is to return the minimum window substring of s that encompasses all the characters in t. If no such substring exists, return an empty string.

Examples:

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

Output: "BANC"

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

Output: "a"

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

Output: ""

2. Solution Steps

1. Use a sliding window approach to traverse the string s.

2. Maintain a map to count the characters in t.

3. Expand the window until it contains all characters of t.

4. Once all characters are included, contract the window from the left to find the smallest valid window.

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

6. Repeat the process until the end of s and return the smallest window found.

3. Code Program

import java.util.HashMap;

public class MinimumWindowSubstring {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t)); // Test the function
    }

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

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

        int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (map.containsKey(c1)) {
                if (map.get(c1) > 0) counter--;
                map.put(c1, map.get(c1) - 1);
            }
            end++;

            while (counter == 0) {
                if (minLen > end - start) {
                    minLen = end - start;
                    minStart = start;
                }

                char c2 = s.charAt(start);
                if (map.containsKey(c2)) {
                    map.put(c2, map.get(c2) + 1);
                    if (map.get(c2) > 0) counter++;
                }
                start++;
            }
        }

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

Output:

"BANC"

Explanation:

1. minWindow: This function identifies the minimum window substring in s that contains all the characters of t.

2. A HashMap is used to store the count of each character in t.

3. The sliding window expands by moving end until it covers all characters in t.

4. The window then contracts by moving start while maintaining all characters of t in the window.

5. During the contraction, the function keeps track of the smallest window that covers all characters in t.

6. After traversing s, the function returns the smallest window found. If no valid window is found, it returns an empty string.

7. This method effectively utilizes the sliding window technique, offering an efficient way to solve the problem with a time complexity of O(n).