The Minimum Window Substring problem is a classic problem in string manipulation and is frequently encountered in coding interviews and real-world applications. In this blog, we’ll explore the problem, understand its solution, and discuss the implementation details.

Problem Statement

Given two strings s and t, we are tasked with finding the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, we return an empty string.

For example, given:

s = "ADOBECODEBANC"
t = "ABC"

The minimum window substring containing all characters from t is "BANC".

Approach

To solve this problem efficiently, we can use the sliding window technique. The idea is to maintain two pointers, left and right, that define the window. We move the right pointer to expand the window until it contains all characters from t. Then, we move the left pointer to shrink the window while maintaining the required characters in the window. We keep track of the minimum window length and its starting index as we traverse the string s.

Solution

Let’s take a closer look at the solution:

class Solution {
    public String minWindow(String s, String t) {
        int[] freq = new int[128]; 
        for (char c : t.toCharArray()) {
            freq[c]++;
        }

        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        int count = t.length();

        while (right < s.length()) {
            if (freq[s.charAt(right)] > 0) {
                count--;
            }
            freq[s.charAt(right)]--;
            right++;

            while (count == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    minStart = left;
                }

                char leftChar = s.charAt(left);
                freq[leftChar]++;
                if (freq[leftChar] > 0) {
                    count++;
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

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