# 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).

For example,

`S = "STUVSTV"`

`T = "STV"`

Minimum window is `"STUV"`.

This is one of the most common and favorite interview questions for engineers.

Lets start with creating the counter, which will keep count of characters. It could a `HashMap`.

```counter:
[ S -1, T-1, V-1 ]
Start with two pointers, maintaining the index of string S:
start, end = 0
have a length variable set to length of T string.
length = 3
```
• Start incrementing the end index.
• Check at the end index of `S`, if the character is in counter map and count > 0, decrement the length.
• keep doing it until length is 0. When length is zero, it means we found a window which contains all the characters from string.`T`
• The length of string is the difference between `end - start`. Track whether the difference is minimum.
• Now start incrementing the start pointer, unless one of the input character is found. Track whether the difference is minimum between `end - start.`
• Continue until end of string `S` is reaced.

Lets look at the above example

```counter:
[ S -1, T-1, V-1 ]
start,end = 0
length = 3
S = "STUVSTV"
T = "STV"

at start = 0, end = 0, S[end] = 'S'
update:
[ S -0, T-1, V-1 ]
incr end: start = 0, end = 1
length = 2

at start = 0, end = 1, S[end] = 'T'
update:
[ S -0, T-0, V-1 ]
incr end: start = 0, end = 2
length = 1

at start = 0, end = 2, S[end] = 'U'
update:
[ S -0, T-0, V-1 ]
incr end: start = 0, end = 3
length = 1

at start = 0, end = 3, S[end] = 'V'
update:
[ S -0, T-0, V-0 ]
incr end: start = 0, end = 3
length = 0
window = end-start+1 = 4 "STUV"

at start = 1, end = 3, S[start] = 'S'
update:
[ S-1, T-0, V-0 ]
incr start: start = 1, end = 3
length = 1

at start = 1, end = 4, S[end] = 'S'
update:
[ S-0, T-0, V-0 ]
incr end: start = 1, end = 3
length = 0
window = end-start+1 = 4 "TUVS"

at start = 1, end = 4, S[start] = 'S'
update:
[ S-0, T-1, V-0 ]
incr start: start = 2, end = 4
length = 1

at start = 2, end = 5, S[end] = 'T'
update:
[ S-0, T-0, V-0 ]
incr end: start = 2, end = 6
length = 0
window = end-start+1 = 4 "UVST"

at start = 2, end = 5, S[end] = 'U'
update:
[ S-0, T-0, V-0 ]
incr start: start = 3, end = 6
length = 0

at start = 3, end = 5, S[start] = 'V'
update:
[ S-0, T-0, V-1 ]
incr start: start = 4, end = 6
length = 1

at start = 4, end = 5, S[end] = 'V'
update:
[ S-0, T-0, V-0 ]
incr end: start = 4, end = 6
length = 0
window = end-start+1 = 3 "STV"
```
``````public class MinWindowSubString {

public static void main(String[] args) {
System.out.println(new MinWindowSubString()
}

String minWindow(String s, String t) {
int maxWind = Integer.MAX_VALUE;
int tArr[] = new int;
for (char ch : t.toCharArray()) {
tArr[ch] = tArr[ch] + 1;
}
int end = 0;
int begin = 0;
int counter = t.length();
int head = begin;
while (end < s.length()) {
if (tArr[s.charAt(end)] > 0) {
counter--;
tArr[s.charAt(end)]--;
}
end--;
while (counter == 0) {
if (end - begin < maxWind) {
maxWind = end - begin;