3306. Count of Substrings Containing Every Vowel and K Consonants II

MediumView on LeetCode

Hash Table String Sliding Window

Time: O(n)

Space: O(1)

Intuition

Count substrings where every vowel appears at least once and count of consonants is divisible by k. Sliding window.

Algorithm

1Sliding window tracking vowel presence (bitmask) and consonant count mod k.
2Count windows where all 5 vowels present and consonants%k==0.

Common Pitfalls

•Two conditions: all vowels present (5-bit mask = 31) AND consonant count % k == 0. Tricky sliding window.

3306.cs

// Approach: Sliding window; count subarrays with all vowels + exactly k consonants using overflow.
// Time: O(n) Space: O(1)

public class Solution
{
    public long CountOfSubstrings(string word, int k)
    {
        return F(word, k) - F(word, k + 1);
    }

    private long F(string word, int k)
    {
        long ans = 0;
        int l = 0, x = 0;
        Dictionary<char, int> cnt = new Dictionary<char, int>();
        foreach (char c in word)
        {
            if (Vowel(c))
            {
                if (cnt.ContainsKey(c))
                    cnt[c]++;
                else
                    cnt[c] = 1;
            }
            else
                x++;
            while (x >= k && cnt.Count == 5)
            {
                char d = word[l++];
                if (Vowel(d))
                {
                    if (cnt.ContainsKey(d))
                    {
                        cnt[d]--;
                        if (cnt[d] == 0)
                            cnt.Remove(d);
                    }
                }
                else
                    x--;
            }
            ans += l;
        }
        
        return ans;
    }

    private bool Vowel(char c)
    {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

Was this solution helpful?