# Minimum Window Substring

`String`, `Two Pointers`, `Sliding Window`

Hard

## Question

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Notice

If there is no such window in source that covers all characters in target, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.

Clarification

Should the characters in minimum window has the same order in target?

Not necessary.

Example

For source = `"ADOBECODEBANC"`, target = `"ABC"`, the minimum window is `"BANC"`

Challenge

Can you do it in time complexity O(n) ?

Tags

## Analysis

``````1. Use two pointers: start and end to represent a window.
2. Move end to find a valid window.
3. When a valid window is found, move start to find a smaller window.
``````

## Solution

``````public class Solution {

/**
* @param source: A string
* @param target: A string
* @return: A string denote the minimum window
*          Return "" if there is no such a string
*/
public String minWindow(String source, String target) {
if (source == null || source.length() == 0 ||
target == null || target.length() == 0) {
return "";
}
int[] sourceHash = new int[256];
int[] targetHash = new int[256];
int ans = Integer.MAX_VALUE;
String minStr = "";

initTargetHash(targetHash, target);

int i = 0;
int j = 0;

for (i = 0; i < source.length(); i++) {
while (j < source.length() && !isValid(sourceHash, targetHash)) {
sourceHash[source.charAt(j)]++;
if (j < source.length()) {
j++;
} else {
break;
}
}
if (isValid(sourceHash, targetHash)) {
if (ans > j - i) {
ans = Math.min(ans, j - i);
minStr = source.substring(i, j);
}
}
sourceHash[source.charAt(i)]--;
}
return minStr;
}
boolean isValid(int[] sourceHash, int[] targetHash) {
for (int i = 0; i < sourceHash.length; i++) {
if (targetHash[i] > sourceHash[i]) {
return false;
}
}
return true;
}

public void initTargetHash(int[] targetHash, String target) {
for (int i = 0; i < target.length(); i++) {
targetHash[target.charAt(i)]++;
}
}
}
``````

#### Approach - Sliding Window - Two Pointer

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems/25848

``````public String minWindow(String s, String t) {
HashMap<Character,Integer> map = new HashMap();
for(char c : s.toCharArray())
map.put(c,0);
for(char c : t.toCharArray())
{
if(map.containsKey(c))
map.put(c,map.get(c)+1);
else
return "";
}

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.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);
map.put(c2, map.get(c2) + 1);

if(map.get(c2) > 0)
counter++;

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

## Reference

##### Here is a 10-line template that can solve most 'substring' problems

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems