# Minimum Window Substring

This page explains Java solution to problem `Minimum Window Substring` using `Sliding window`.

## Problem Statement

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example 1:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class MinimumWindowSubstring {
public String minWindow(String s, String t) {
if(s == null || t == null) return "";

HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}

int start = 0;
int end = 0;
int required = t.length();
int minLength = Integer.MAX_VALUE;
int minStart = 0;
while(end < s.length()) {
char ch = s.charAt(end);
if(map.containsKey(ch)) {
if(map.get(ch) > 0) required--;
map.put(ch, map.get(ch) - 1);
while(required == 0) {
if(minLength > end - start) {
minLength = end - start + 1;
minStart = start;
}
char c = s.charAt(start);
if(map.containsKey(c)) {
map.put(c, map.getOrDefault(c, 0) + 1);
if(map.get(c) > 0) required++;
}
start++;
}
}
end++;
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLength);
}
}
``````

## Time Complexity

O(N + M) Where
N is total number of elements in an input search string.
M is total number of elements in an input string which needs to be searched.

## Space Complexity

O(M) Where
M is total number of elements in an input string which needs to be searched.