Minimum Window Substringhttps://leetcode.com/problems/minimum-window-substring/
- 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