**Solution**

**Minimum Window Substring**https://leetcode.com/problems/minimum-window-substring/

**Algorithm**

- The key thing to note here is that characters in t are not supposed to be unique.
- S = "aa". T = "aa" - Solution is "aa".
- We keep two pointers start and end initialized to 0.
- Now move the end pointer to the right unitl we find a solution.
- When we find a solution, we try to optimize it - we move the start pointer as much as we can to right without breaking the constraints.

```
from collections import Counter, defaultdict
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
st, c1, min_so_far, result, fmap = 0, Counter(t), len(s)+1, "", defaultdict(int)
unique_ch = len(c1)
for end in range(len(s)):
if s[end] in c1:
fmap[s[end]] += 1
if fmap[s[end]] == c1[s[end]]:
unique_ch -= 1
while st <= end and unique_ch == 0:
if end - st + 1 < min_so_far:
min_so_far, result = end - st + 1, s[st:end+1]
if s[st] in fmap:
fmap[s[st]] -= 1
if fmap[s[st]] < c1[s[st]]:
unique_ch += 1
st += 1
return result
```

**General Pattern to solve 2 pointer problems**

```
start, end = 0, len(input)
// data-structures for your problem
for end in range(len(input)):
if input[end] contributes to extending the solution:
update the impact of including input[end]
while st <= end and input[st:end+1] is a valid solution:
update for optimal solution
update for the impact of removing input[start]
start += 1
```