# 76. Minimum Window Substring

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/