“This is the 25th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

76. Minimum coverage substring

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:

  • fortThe number of characters in the substring we are looking for must not be less than the number of characters in t.
  • ifsThere is such a substring in, and 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

Example 3

Input: s = "a", t = "aa" Output: "" Explanation: both characters 'a' in t should be included in the substring of S, so there is no qualified substring, return empty string.Copy the code

prompt

  • 1 <= s.length, t.length <= 10^5
  • s 和 tConsists of English letters

** Can you design an algorithm to solve this problem in o(n) time?

The code template

/ * * *@param {string} s
 * @param {string} t
 * @return {string}* /
var minWindow = function (s, t) {};
Copy the code

solution

The problem can be solved by using the for loop method. The problem can be solved by using the for loop method. The problem can be solved by using the for loop method. Find the searched string in terms of the length of t, which is the target string, which is s for all combinations of the same length as t

A less violent solution is to use JS split strings to solve the problem, reuse for twice

If you follow the above solution, the time complexity must be O(n^2), generally will timeout, but this problem can actually have a simpler method, that is, sliding window to solve the problem

That may someone want to ask, how is this sliding window a sliding method?

Sliding window first, and also is a kind of double pointer, can be said to be about pointer with one side version, it is thought, right pointer first, find the qualified window, and then the left pointer to narrow window to find qualified smaller window, because the pointer moving around, so that the length of the window is constantly changing, so also called sliding window, detailed below

So the most important thing about this sliding window

  1. The right pointer finds the window
  2. Left pointer zooms out the window

The algorithm of sliding window is to write around the above two, first determine to find the window, is according to [left, right] this window interval contains our T, here some people may think of using JS related API to solve, this is not impossible, but we can use a more low-level way to solve this problem

const s = "ABCDE";
const t = "BCD";
s.slice(left, right + 1).match(t);
Copy the code

The lower level is the way to store the characters in T in a hash table. The hash table is assumed to be need, and the value is the number of times a character appears in T, that is, to call the Map API of JS. Note that the characters in T can be repeated, and this is also highlighted in the title. This is just to keep us from misjudging Windows, like t = ‘aa’

Then maintain a hash table for the number of occurrences of t characters in the window (using JS to dynamically generate a key-value pair is also ok), this hash table is assumed to be windowCount, when we move the left and right pointer to maintain this hash table, When the need is the same as the key-value pair in windowCount, the window can be shrunk as follows

Since our need and windowCount are both reference types, it’s impossible to compare them directly, so we’re going to have to maintain a variable to see if they’re equal, and let’s say this variable is valid, and when we maintain this variable, Use the same number of key-value pairs in windowCount as in need, as follows

When we finally shrink the window, it’s the same operation as when we move the right pointer to find the window, but instead of expanding the window to shrink the window, but when we shrink the window, the most important thing is to maintain our answer, which is the minimum covering substring

The entire window movement ends when the right pointer reaches the end of S and the left pointer shrinks the window

The solution is as follows

var minWindow = function (s, t) {
  const need = new Map(a);const windowCount = new Map(a);for (let i = 0; i < t.length; i++) {
    need.set(t[i], need.has(t[i]) ? need.get(t[i]) + 1 : 1);
    windowCount.set(t[i], 0);
  }
  let left = 0,
    right = 0;
  let valid = 0;
  let start = 0,
    len = Number.MAX_SAFE_INTEGER;
  while (right < s.length) {
    const c = s.charAt(right);
    right++;
    if (need.has(c)) {
      windowCount.set(c, windowCount.get(c) + 1);
      if(windowCount.get(c) === need.get(c)) { valid++; }}while (valid === need.size) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      const c = s.charAt(left);
      left++;
      if (need.has(c)) {
        if (windowCount.get(c) === need.get(c)) {
          valid--;
        }
        windowCount.set(c, windowCount.get(c) - 1); }}}return len === Number.MAX_SAFE_INTEGER ? "" : s.slice(start, start + len);
};
Copy the code

This solution is actually derived from Labuladong’s sliding window frame solution, but JS using Map in sliding window may be a little redundant, if it is minimalist, you can consider using array replacement or using JS Object to dynamically add attributes, etc. But the most important part of the algorithm is still the idea of sliding Windows, and it’s good to have different data structures to store needs or Windows