Question 76 from Leetcode.

Topic describes

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.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" output: "BANC"Copy the code

Example 2:

Input: s = "a", t = "a" output: "a"Copy the code

Tip:

  • 1 <= s.length, t.length <= 105
  • S and T consist of English letters

Their thinking

  • First the substring T is iterated and the map value is set. For example: substring t = “ABC”, the Map (3) {” A “= > 1,” B “= > 1,” C “= > 1}. Record the map size value.

  • Then the right pointer goes backwards. For each character found in the map, the value of the character is reduced by 1. When the value of the character is reduced to 0, the map size is reduced by 1.

  • Until the map’s size is 0, the left pointer is moved and the current substring is recorded.

  • For each character found in the left pointer, set map and size to 1. Then continue the loop and move the right pointer. The next time the map size is reduced to 0, move the left pointer.

  • Each time the left pointer starts to move, the current substring meets the requirements of the question. The shortest substring that meets the requirements can be obtained by comparing the length of the substring and taking the smallest substring.

The code shown

Double pointer + hash table + sliding window + string

/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { const len = s.length; const map = new Map(); let l = 0, r = 0, res = ''; for (let i = 0; i < t.length; i++) { const c = t[i]; map.set(c, map.get(c) ? map.get(c) + 1 : 1); } let mapSize = map.size; while (r < len) { const c1 = s[r]; if (map.has(c1)) { map.set(c1, map.get(c1) - 1) if (map.get(c1) === 0) mapSize -= 1; } while(mapSize === 0) { const newRes = s.substring(l, r + 1); if (! res || res.length > newRes.length) { res = newRes; } const c2 = s[l]; if (map.has(c2)) { map.set(c2, map.get(c2) + 1); if (map.get(c2) === 1) mapSize += 1; } l += 1; } r += 1; } return res; }Copy the code

Complexity analysis:

Time complexity: O(m + N). M is the length of string s, n is the length of string t.

Space complexity: O(k). K is the length of a non-repeating character in t.

conclusion

This is useful for understanding double Pointers, sliding Windows, and map data types and string manipulation.