DDSA Solutions

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

MediumView on LeetCode
Hash TableStringSliding Window
Time: O(n)
Space: O(1)

Problem Overview

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

Intuition

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

Algorithm

  1. 1Sliding window tracking vowel presence (bitmask) and consonant count mod k.
  2. 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
C#
// 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?

Related Problems