The title

I give you a string S, a string t. Returns the smallest string in S that covers all characters of t. Return an empty string “” if there is no substring in S that covers all characters of t.

Note: if such a substring exists in S, we guarantee that it is the only answer.

Link: leetcode-cn.com/problems/mi…

Their thinking

1. Find all substrings containing T

2. Find the smallest substring and return it

The problem solving steps

2. Move the right pointer to find the substring containing T, and move the left pointer to minimize the length of the substring containing T 3. Loop through the above steps to find the smallest substring containing T

code

/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { let l = 0; let r = 0; let res = ''; Const need = new Map() for(let v of t){need.set(v,need.has(v)? need.get(v) ++ : 1)} let needType = need.size while(r < s.length){const c = s[r] If (need.has(c)){need.set(c,need.get(c) -1) / Need.get (c) === 0) needType -= 1} while(needType === 0) {const newArr = s.substring(l,r+1) if(! res || newArr.length < res.length) res = newArr const c2 = s[l] if(need.has(c2)){ need.set(c2, need.get(c2) + 1) if(need.get(c2) === 1) needType += 1 } l ++ } r ++; } return res };Copy the code

Time complexity and space complexity

Time complexity: O(m+n) m is the length of T, and n is the length of S. Space complexity: O(m) m is the number of different characters in T