1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution
{
public:
    string minWindow(string s, string t)
    {
        std::unordered_map<char, int> hashS, hashT;
        for (char c : t)
            ++ hashT[c]; // 记录目标字符串 t 的字符频率

        int cnt = 0; // 当前窗口内满足条件的字符个数
        std::string res; // 记录结果子串
        for (int i = 0, j = 0; i < s.size(); ++i)
        {
            ++ hashS[s[i]]; // 扩展窗口
            if (hashS[s[i]] <= hashT[s[i]])
                ++ cnt; // 更新满足条件的字符数

            // 收缩窗口：移除多余的字符
            while (hashS[s[j]] > hashT[s[j]])
            {
                -- hashS[s[j]];
                ++ j;
            }

            // 检查当前窗口是否满足条件
            if (cnt == t.size())
                if (res.empty() || res.size() > i - j + 1)
                    res = s.substr(j, i - j + 1); // 更新结果
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
  def minWindow(self, s: str, t: str) -> str:
    freqS, freqT = defaultdict(int), defaultdict(int)
    for c in t:
      freqT[c] += 1

    j, cnt = 0, 0
    res = ""
    for i in range(len(s)):
      freqS[s[i]] += 1
      if freqS[s[i]] <= freqT[s[i]]:
        cnt += 1
      while j < len(s) and freqS[s[j]] > freqT[s[j]]:
        freqS[s[j]] -= 1
        j += 1
      if cnt == len(t):
        if not res or len(res) > i - j + 1:
          res = s[j : i + 1]
    return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func minWindow(s string, t string) string {
  freqS, freqT := make(map[byte]int), make(map[byte]int)
  for i := 0; i < len(t); i ++ {
    freqT[t[i]] ++ ;
  }

  cnt := 0
  res := ""
  for i, j := 0, 0; i < len(s); i ++ {
    freqS[s[i]] ++
    if freqS[s[i]] <= freqT[s[i]] {
      cnt ++
    }
    for j < len(s) && freqS[s[j]] > freqT[s[j]] {
      freqS[s[j]] --
      j ++
    }
    if (cnt == len(t)) {
      if (res == "" || len(res) > i - j + 1) {
        res = s[j : i + 1]
      }
    }
  }
  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  let freqS = new Map(),
    freqT = new Map();
  for (let c of t) {
    freqT.set(c, (freqT.get(c) || 0) + 1);
  }

  let cnt = 0;
  let res = "";
  for (let i = 0, j = 0; i < s.length; i++) {
    freqS.set(s[i], (freqS.get(s[i]) || 0) + 1);
    if (freqS.get(s[i]) <= freqT.get(s[i])) {
      cnt++;
    }
    while (freqS.get(s[j]) > (freqT.get(s[j]) || 0)) {
      freqS.set(s[j], freqS.get(s[j]) - 1);
      j++;
    }
    if (cnt == t.length) {
      if (res.length == 0 || res.length > i - j + 1) {
        res = s.slice(j, i + 1);
      }
    }
  }
  return res;
};