滑动窗口

03. 无重复字符的最长子串 (opens new window)

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

题解

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const set = new Set();
  let countMax = 0;
  let [l, r] = [0, 0];
  if(s.length<=1) return s.length

  while (r <= s.length - 1) {
    if (set.has(s[r])) {
      // 注意这里是删除s[l] 因为窗口向右滑动 删除开头的字母
      set.delete(s[l]);
      l++;
    } else {
      countMax = Math.max(countMax, r - l + 1);
      set.add(s[r])
      r++
    }
  }

  return countMax;
};

76. 最小覆盖子串 (opens new window)

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "aa", t = "aa"
输出："aa"
解释：整个字符串 s 是最小覆盖子串。

示例 3：

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

题解

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  // 思路
  // 一直r++到能覆盖t为止 记录长度
  // 然后l++ 如果还能覆盖 记录长度 如果不够 则 停止, 继续重复上面一步

  let res = "";
  // 长度先给一个最大值 不然后面比较长度的时候都不会比他小
  let resLen = Number.MAX_SAFE_INTEGER;

  let l = 0,
    r = 0;
  // 比如abbc charCount最大就是3 b两个都减完了 这个数-1 当他为0的时候 说明当前是一个备选目标答案
  let charCount = new Set(t.split("")).size;
  // key:char value初始是char在t的个数, 等于0的时候,说明这个char够了, 可以给count+1
  let map = new Map();

  for (char of t) {
    map.set(char, (map.get(char) || 0) + 1);
  }

  // l++的过程
  while (r <= s.length - 1) {
    // 是目标char
    if (t.includes(s[r])) {
      // 处理map和count
      map.set(s[r], map.get(s[r]) - 1);

      // 这时候s[r]字母 齐了 (可能会有负数, 所以等于0的时候就要记录一次)
      if (map.get(s[r]) === 0) {
        // charCount先-1  再判断子串字母是否都齐了
        if (--charCount === 0) {
          if (r - l + 1 < resLen) {
            resLen = r - l + 1;
            res = s.slice(l, r + 1);
          }

          // 齐了的时候开始l++
          while (charCount === 0) {
            if (r - l + 1 < resLen) {
              resLen = r - l + 1;
              res = s.slice(l, r + 1);
            }

            if (t.includes(s[l])) {
              // 如果当前是0的话, 代表马上就不够了
              if (map.get(s[l]) === 0) {
                charCount++;
              }
              map.set(s[l], map.get(s[l]) + 1);
            }
            l++;
          }
        }
      }
    }

    r++;
  }

  return res;
};