发表于 2025.01.10

• 典型滑动窗口题目，统计word2的字符出现频次，以及word1当前窗口的字符出现频次，如果word1当前窗口每个字符的出现频次均大于等于word2的频次，则说明可以通过重新排列word1的滑动窗口内的字串得到word2，以及固定窗口左侧，一直延伸到word1的末尾的所有子串都满足题目要求。

  II属于困难题，上述的做法会超时。改进点可以使用一个变量diff记录word1当前窗口还需要多少个字符才能通过重新排列得到word2，然后在滑动窗口的过程中，根据diff的值来判断是否需要移动窗口左侧或者右侧。diff值可以在窗口变化时更新，判断当前滑走/滑入的字符是否会影响diff的值来采取递增或者递减。

  第一题做法：

  class Solution {
  public:
      auto count(const string& word, int left, int right) {
          vector<int> _res(26, 0);
          for (int i = left; i < right; ++i) _res[word[i] - 'a']++;
          return _res;
      };
  
      auto match(const vector<int> &cur_word1_sub_cnt, const vector<int> &word2_cnt) {
          for (int i = 0; i < 26; ++i) if (cur_word1_sub_cnt[i] < word2_cnt[i]) return false;
          return true;
      }
  
      long long validSubstringCount(string word1, string word2) {
          if (word1.size() < word2.size()) return 0;
  
          long long ans = 0;
          auto word2_cnt = count(word2, 0, word2.size());
          auto cur_word1_sub_cnt = count(word1, 0, word2.size());
          int left = 0, right = word2.size() - 1;
          while (right < word1.size()) {
              if (match(cur_word1_sub_cnt, word2_cnt)) {
                  ans += word1.size() - right;
                  --cur_word1_sub_cnt[word1[left++] - 'a'];
              } else {
                  ++right;
                  if (right < word1.size())
                      ++cur_word1_sub_cnt[word1[right] - 'a'];
              }
          }
  
          return ans;
      }
  };

  第二题的做法：

  class Solution {
  public:
      auto count(const string& word, int left, int right) {
          vector<int> _res(26, 0);
          for (int i = left; i < right; ++i) _res[word[i] - 'a']++;
          return _res;
      };
  
      long long validSubstringCount(string word1, string word2) {
          if (word1.size() < word2.size()) return 0;
  
          long long ans = 0;
          auto word2_cnt = count(word2, 0, word2.size());
          auto cur_word1_sub_cnt = count(word1, 0, word2.size());
          int diff = 0;
          // diff表示word1当前窗口还需要多少个字符才能通过重新排列得到word2
          // 注意如果word1当前窗口的某个字符出现次数超过word2的次数，不需要减去， 说明已经满足了
          for (int i = 0; i < 26; ++i) diff += max(0, word2_cnt[i] - cur_word1_sub_cnt[i]);
  
          int left = 0, right = word2.size() - 1;
          while (right < word1.size()) {
              if (diff == 0) {
                  ans += word1.size() - right;
                  --cur_word1_sub_cnt[word1[left] - 'a'];
                  // 如果减去后的该字符次数小于word2的次数，说明需要增加diff
                  // 如果仍然大于等于word2的次数，说明还是处于满足状态，不需要增加diff
                  if (cur_word1_sub_cnt[word1[left] - 'a'] < word2_cnt[word1[left] - 'a']) ++diff;
  
                  ++left;
              } else {
                  ++right;
                  if (right < word1.size()) {
                      ++cur_word1_sub_cnt[word1[right] - 'a'];
                      // 同理
                      if (cur_word1_sub_cnt[word1[right] - 'a'] <= word2_cnt[word1[right] - 'a']) --diff;
                  }
              }
          }
  
          return ans;
      }
  };

• LC 题目链接