Day 9

The shortest string containing all characters

• Difficulty: difficulty
• Method: double pointer

The title

• Given two strings s and t. Returns the shortest substring of all characters in s that contain t. An empty string “” is returned if no substring exists in s.
• If there are multiple substrings in s, return any one of them.
• Note: For repeated characters in t, we must look for substrings that have at least the number of characters in t.

The sample

Enter: s ="ADOBECODEBANC", t = "ABC"Output:"BANC"Explanation: Shortest substring"BANC"Contains all characters of the string t'A','B','C'
Copy the code

Enter: s ="a", t = "a"Output:"a"
Copy the code

Enter: s ="a", t = "aa"Output:""Explanation: two characters in t'a'Should be contained in the substring of S, so there is no eligible substring, return empty string.Copy the code

prompt

• 1 <= s.length, t.length <= 105
• s 和 tConsists of English letters

solution

/ * * *@param {string} s
 * @param {string} t
 * @return {string}* /
var minWindow = function(s, t) {
  let map1 = new Map(a);// Process data
  for (let i = 0; i < t.length; i++) {
    if (map1.has(t[i])) {
      map1.set(t[i], map1.get(t[i]) + 1);
    }else {
      map1.set(t[i], 1); }}// console.log('map1', map1);
  // Start pointer
  let start = 0;
  // End pointer
  let end = 0;
  // New record collection
  let map2 = new Map(a);// Store the length of the matching character found
  let len = 0;
  // Record the successful data set
  let str = ' ';
  // Determine the length
  let minLen = Infinity;
  // Record the final result
  let ans = -1;
  while (end < s.length) {
    / / meet
    if (map1.has(s[end])) {
      // Write it down
      if (map2.has(s[end])) {
        map2.set(s[end], map2.get(s[end]) + 1);
      }else {
        map2.set(s[end], 1);
      }
      // console.log('start',start,'end',end,'2end',map2.get(s[end]),'1end',map1.get(s[end]));
      // Len length ++ only if map1 is greater than or equal to map2
      if (map2.get(s[end]) <= map1.get(s[end])) {
        len++;
      }
      // console.log('len', len);
      // The length of len must be the same
      if (len == t.length) {
        / / the console. The log (' up to standard, len, 'start, start,' end ', end);
        // Store the output as a string from start to end
        if (minLen >= (end - start + 1)) {
          ans = start;
          minLen = end - start + 1;
        }
        // Process start, let start look for breaking the standard after stop
        while (start <= end) {
          // console.log('minLen', minLen);
          // Contains start
          if (map1.has(s[start])) {
            map2.set(s[start], map2.get(s[start]) - 1);
            // console.log('-1',map2.get(s[start]));
          }else {
            start++;
            if (minLen >= (end - start + 1)) {
              ans = start;
              minLen = end - start + 1;
            }
            continue;
          }
          // Determine whether the length needs to be reduced, breaking the balance standard
          if (map2.get(s[start]) < map1.get(s[start])) {
            // console.log('m2',map2.get(s[start]),'m1',map1.get(s[start]));
            len--;
            start++;
            break;
          }else {
            start++;
            if (minLen >= (end - start + 1)) {
              ans = start;
              minLen = end - start + 1;
            }
          }
        }
      }
      end++;
    }else {
      / / not satisfiedend++; }}if (ans == -1) {
    return ' ';
  }else {
    let str = ' ';
    for (let i = ans; i < ans + minLen; i++) {
      str += s[i];
    }
    returnstr; }};Copy the code

The appendix

• Double pointer
• I’m on the right track. I’m also going to write out the pseudocode