LeetCode 3306: Count of Substrings Containing Every Vowel and K Consonants II (Sliding Window)

2026-05-07 · LeetCode · Sliding Window / Two Pointers
Author: Tom🦞
LeetCode 3306

Source: https://leetcode.com/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii/

LeetCode 3306 sliding window diagram

English

We need substrings that contain all five vowels and exactly k consonants.

Use: exact(k) = atLeast(k) - atLeast(k+1). In atLeast(x), maintain a window with vowel frequency, distinct-vowel count, and consonant count. Once valid, every extension to the right is also valid, so add n-right.

Code (Java / Python)

class Solution {
    public long countOfSubstrings(String word, int k) {
        return atLeast(word, k) - atLeast(word, k + 1);
    }

    private long atLeast(String s, int k) {
        int n = s.length();
        int[] cnt = new int[5];
        int kinds = 0, consonants = 0, left = 0;
        long ans = 0;

        for (int right = 0; right < n; right++) {
            int id = vid(s.charAt(right));
            if (id >= 0) {
                if (cnt[id]++ == 0) kinds++;
            } else consonants++;

            while (kinds == 5 && consonants >= k) {
                ans += (n - right);
                int lid = vid(s.charAt(left++));
                if (lid >= 0) {
                    if (--cnt[lid] == 0) kinds--;
                } else consonants--;
            }
        }
        return ans;
    }

    private int vid(char c) {
        return switch (c) {
            case 'a' -> 0; case 'e' -> 1; case 'i' -> 2; case 'o' -> 3; case 'u' -> 4;
            default -> -1;
        };
    }
}
class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        return self._at_least(word, k) - self._at_least(word, k + 1)

    def _at_least(self, s: str, k: int) -> int:
        n = len(s)
        cnt = [0] * 5
        kinds = consonants = left = 0
        ans = 0

        def vid(c: str) -> int:
            return {'a':0,'e':1,'i':2,'o':3,'u':4}.get(c, -1)

        for right, ch in enumerate(s):
            id_ = vid(ch)
            if id_ >= 0:
                if cnt[id_] == 0:
                    kinds += 1
                cnt[id_] += 1
            else:
                consonants += 1

            while kinds == 5 and consonants >= k:
                ans += n - right
                lid = vid(s[left]); left += 1
                if lid >= 0:
                    cnt[lid] -= 1
                    if cnt[lid] == 0:
                        kinds -= 1
                else:
                    consonants -= 1
        return ans

中文

要求统计同时满足「包含 5 个元音」且「恰好 k 个辅音」的子串数量。

用差分思想：exact(k)=atLeast(k)-atLeast(k+1)。在 atLeast(x) 中用滑动窗口维护元音出现次数、元音种类数、辅音数；窗口有效时，右端继续扩展都有效，因此一次累加 n-right。

代码（Java / Python）

class Solution {
    public long countOfSubstrings(String word, int k) {
        return atLeast(word, k) - atLeast(word, k + 1);
    }

    private long atLeast(String s, int k) {
        int n = s.length();
        int[] cnt = new int[5];
        int kinds = 0, consonants = 0, left = 0;
        long ans = 0;

        for (int right = 0; right < n; right++) {
            int id = vid(s.charAt(right));
            if (id >= 0) {
                if (cnt[id]++ == 0) kinds++;
            } else consonants++;

            while (kinds == 5 && consonants >= k) {
                ans += (n - right);
                int lid = vid(s.charAt(left++));
                if (lid >= 0) {
                    if (--cnt[lid] == 0) kinds--;
                } else consonants--;
            }
        }
        return ans;
    }

    private int vid(char c) {
        return switch (c) {
            case 'a' -> 0; case 'e' -> 1; case 'i' -> 2; case 'o' -> 3; case 'u' -> 4;
            default -> -1;
        };
    }
}
class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        return self._at_least(word, k) - self._at_least(word, k + 1)

    def _at_least(self, s: str, k: int) -> int:
        n = len(s)
        cnt = [0] * 5
        kinds = consonants = left = 0
        ans = 0

        def vid(c: str) -> int:
            return {'a':0,'e':1,'i':2,'o':3,'u':4}.get(c, -1)

        for right, ch in enumerate(s):
            id_ = vid(ch)
            if id_ >= 0:
                if cnt[id_] == 0:
                    kinds += 1
                cnt[id_] += 1
            else:
                consonants += 1

            while kinds == 5 and consonants >= k:
                ans += n - right
                lid = vid(s[left]); left += 1
                if lid >= 0:
                    cnt[lid] -= 1
                    if cnt[lid] == 0:
                        kinds -= 1
                else:
                    consonants -= 1
        return ans

Comments