LeetCode 题解 - 3306. Count of Substrings Containing Every Vowel and K Consonants II

题目链接：3306. Count of Substrings Containing Every Vowel and K Consonants II

You are given a string word and a non-negative integer k.

Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

这是一道典型又不那么典型的滑动窗口题目。典型在，从题干来看，很容易看出来要用滑动窗口。非典型在，直接应用滑动窗口不那么容易。

对于滑动窗口 [left, right)，最重要的就是两点：

1. 在什么条件下增大窗口，即 right++；
2. 在什么条件下减小窗口，即 left++。

从题目来看，

1. 当条件不满足时，即窗口中没有包含所有五个元音，或没有包含 k 个辅音时，我们应当增大窗口。
2. 当条件满足时，即窗口中包含了所有五个元音，且包含 k 个辅音时，我们应当……？

容易发现情况 2 下，我们既可以增大窗口，也可以减小窗口，覆盖所有合法子字符串比较困难。

换个思路。之所以我们在情况 2 下不容易判定对窗口的操作，是因为我们需要保持 k 个辅音的条件。

对于元音来说，只要满足五个元音都存在，扩大窗口也没问题。如果我们在锚定 left 的情况下，扩大窗口找到 [left, right) 满足五个元音都存在，那么我们就找到了 word.size() - right + 1 个子字符串满足五个元音都存在，之后缩小窗口，即 left++ 后再扩大寻找下一个合法窗口即可。

k 个辅音会限制我们扩张窗口，因为扩大窗口可能会导致窗口中辅音数量大于 k。那么我们可以改一下条件：窗口中至少存在 k 个辅音。这样一来，窗口的缩小和扩大逻辑和元音就一样了。写成代码就是：

long long countOfSubstringsWithAtLeaseKConsonants(
    const std::string& word,
    const int k) {
  const int kMinWindowSize = k + 5;
  if (word.size() < kMinWindowSize) {
    return 0;
  }

  long long substringCount = 0;
  std::unordered_map<char, int> vowelToCounts;
  int consonantCountInWindow = 0;
  int left = 0;
  int right = 0;

  while (true) {
    if (vowelToCounts.size() < 5 || consonantCountInWindow < k) {
      // We need more letters, expand.

      if (right == word.size()) {
        // Impossible to expand. Break.
        break;
      }

      if (isVowel(word[right])) {
        vowelToCounts[word[right]]++;
      } else {
        consonantCountInWindow++;
      }
      right++;
    } else {
      // [left, right) is a valid window, and can create
      // `word.size() - right + 1` valid substrings.
      substringCount += static_cast<long long>(word.size()) - right + 1;

      // We have discovered all valid substrings starts at `left`. Shrink.
      if (isVowel(word[left])) {
        vowelToCounts[word[left]]--;
        if (vowelToCounts[word[left]] == 0) {
          vowelToCounts.erase(word[left]);
        }
      } else {
        consonantCountInWindow--;
      }
      left++;
    }
  }

  return substringCount;
}

那么怎么得到所有元音都存在，且正好 k 个辅音的子字符串的数量呢？

对于“所有元音都存在，且至少存在 k 个辅音的子字符串”，其包含的子字符串集合是：

1. 所有元音都存在，且有 k 个辅音的子字符串。
2. 所有元音都存在，且有 k + 1 个辅音的子字符串。
3. 所有元音都存在，且有 k + 2 个辅音的子字符串。
4. ……

对于“所有元音都存在，且至少存在 k + 1 个辅音的子字符串”，其包含的子字符串集合是：

1. 所有元音都存在，且有 k + 1 个辅音的子字符串。
2. 所有元音都存在，且有 k + 2 个辅音的子字符串。
3. 所有元音都存在，且有 k + 3 个辅音的子字符串。
4. ……

容易发现，让“所有元音都存在，且至少存在 k 个辅音的子字符串”的数量，减去“所有元音都存在，且至少存在 k + 1 个辅音的子字符串”的数量，就是“所有元音都存在，且正好存在 k 个辅音的子字符串”的数量：

long long countOfSubstrings(const std::string& word, const int k) {
  return countOfSubstringsWithAtLeaseKConsonants(word, k) -
         countOfSubstringsWithAtLeaseKConsonants(word, k + 1);
}

完整代码：

class Solution {
 public:
  long long countOfSubstrings(const std::string& word, const int k) {
    return countOfSubstringsWithAtLeaseKConsonants(word, k) -
           countOfSubstringsWithAtLeaseKConsonants(word, k + 1);
  }

 private:
  static const inline std::unordered_set<char> vowels = {'a', 'e', 'i', 'o',
                                                         'u'};

  static bool isVowel(const char c) { return vowels.contains(c); }

  static long long countOfSubstringsWithAtLeaseKConsonants(
      const std::string& word,
      const int k) {
    const int kMinWindowSize = k + 5;
    if (word.size() < kMinWindowSize) {
      return 0;
    }

    long long substringCount = 0;
    std::unordered_map<char, int> vowelToCounts;
    int consonantCountInWindow = 0;
    int left = 0;
    int right = 0;

    while (true) {
      if (vowelToCounts.size() < 5 || consonantCountInWindow < k) {
        // We need more letters, expand.

        if (right == word.size()) {
          // Impossible to expand. Break.
          break;
        }

        if (isVowel(word[right])) {
          vowelToCounts[word[right]]++;
        } else {
          consonantCountInWindow++;
        }
        right++;
      } else {
        // [left, right) is a valid window, and can create
        // `word.size() - right + 1` valid substrings.
        substringCount += static_cast<long long>(word.size()) - right + 1;

        // We have discovered all valid substrings starts at `left`. Shrink.
        if (isVowel(word[left])) {
          vowelToCounts[word[left]]--;
          if (vowelToCounts[word[left]] == 0) {
            vowelToCounts.erase(word[left]);
          }
        } else {
          consonantCountInWindow--;
        }
        left++;
      }
    }

    return substringCount;
  }
};