We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count of Substrings Containing Every Vowel and K Consonants I

Number: 3570

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string word and a non-negative integer k, count the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

Key Insights

  • We need to check every possible substring.
  • For each substring, count vowels and consonants.
  • The substring is valid if it contains all vowels (each at least once) and exactly k consonants.
  • Since the maximum word length is small (at most 250), an O(n²) solution is acceptable.
  • Early termination is possible during the inner loop when the consonant count exceeds k.

Space and Time Complexity

Time Complexity: O(n²) in the worst case, where n is the length of the string. Space Complexity: O(1) extra space, since we only use a fixed-size frequency counter for vowels and a counter for consonants.

Solution

We can use a brute-force approach using two nested loops. The outer loop selects the starting index of a substring, and the inner loop extends the substring one character at a time. During the inner loop, we maintain a frequency counter for vowels and a count for consonants. If the consonant count exceeds k, we break out of the loop because further extension will only add more consonants. Whenever the consonant count equals k, we check if every vowel has appeared at least once. If so, we increment our result counter.

Data Structures Used:

  • A fixed size dictionary (or array) to keep the count of vowels.
  • Simple integer counter for consonants.

Algorithmic Approach:

  1. Iterate with two pointers for all possible substrings.
  2. For each character, update the vowel frequency if it is a vowel; otherwise, update the consonant count.
  3. If the number of consonants exceeds k, break out of the current inner loop.
  4. When exactly k consonants are reached, check if all five vowels have been seen at least once. If yes, count the substring.
  5. Continue until all substrings are examined.

Code Solutions

# Python solution for Count of Substrings Containing Every Vowel and K Consonants I

def count_substrings(word: str, k: int) -> int:
    n = len(word)
    result = 0
    vowels = {'a', 'e', 'i', 'o', 'u'}

    # Iterate over all possible starting indexes for the substring
    for i in range(n):
        # Dictionary to count occurrences of vowels
        vowel_count = {v: 0 for v in vowels}
        consonant_count = 0

        # Expand the substring with ending index j
        for j in range(i, n):
            char = word[j]
            # Check if character is a vowel
            if char in vowels:
                vowel_count[char] += 1
            else:
                consonant_count += 1

            # If consonants exceed k, break out of the inner loop
            if consonant_count > k:
                break

            # When exactly k consonants, verify that every vowel is present at least once
            if consonant_count == k and all(vowel_count[v] > 0 for v in vowels):
                result += 1

    return result

# Example usage:
print(count_substrings("aeioqq", 1))  # Expected output: 0
print(count_substrings("aeiou", 0))   # Expected output: 1
print(count_substrings("ieaouqqieaouqq", 1))  # Expected output: 3
← Back to All Questions