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 II

Number: 3569

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

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

Key Insights

  • Count of consonants in any substring can be quickly computed via a prefix‐sum array.
  • The “vowel condition” (each vowel appears at least once in the substring) can be reduced to: for a substring word[i…r], every vowel must appear in the segment, which is equivalent to i being at most the smallest (i.e. leftmost) occurrence among the latest appearances of all vowels up to r.
  • Rewriting the consonant requirement: if we define pre[i] as the number of consonants in word[0..i-1], then the substring word[i…r] has exactly k consonants if and only if pre[r+1] – pre[i] = k.
  • Therefore, for every index r where all vowels have been seen somewhere in word[0…r], a valid starting index i for a substring ending at r must satisfy: • i ≤ min(vowelLastOccurrence) where vowelLastOccurrence is maintained for each vowel, and • pre[i] = pre[r+1] – k.
  • In order to “count” such starting indices fast, we precompute an array pre of length n+1 and for every possible value add the indices i (from 0 to n) to a mapping from pre-value to a sorted list of indices. Then, for each r (0 ≤ r < n) where all vowels are available, we can binary‐search in that sorted list for indices ≤ validLimit.
  • Finally, the answer is the sum over all r of the number of valid starting positions i that create a valid substring ending at r.

Space and Time Complexity

Time Complexity: O(n log n) – Building the prefix sum array takes O(n), and for each of the n positions we perform a binary search on a sorted list. Space Complexity: O(n) – for storing the prefix array and the mapping from prefix count to a list of indices.

Solution

We use the following approach:

  1. Build a prefix sum array pre where pre[0] = 0 and for 1 ≤ i ≤ n, pre[i] = pre[i-1] + 1 if word[i-1] is a consonant; otherwise pre[i] remains the same.
  2. For every index i from 0 to n of the pre array, group the indices by their pre[i] value into a dictionary. This will allow us to answer queries: “How many indices i are ≤ X such that pre[i] equals a target value?”
  3. As we iterate over each character in word (index r from 0 to n–1), we update a vowelLast dictionary (for vowels a, e, i, o, u) to record the last occurrence of each vowel.
  4. Whenever all vowels have been seen (i.e. none have an initial value of –1), define validLimit as the minimum value among vowelLast. For the substring ending at r, the condition for exactly k consonants becomes pre[r+1] – pre[i] = k ⟹ pre[i] = pre[r+1] – k.
  5. Use binary search on the sorted list corresponding to target = pre[r+1] – k to count how many indices i (with i between 0 and validLimit) exist.
  6. Sum over all valid r and return the answer.

This solution makes use of prefix sums, a dictionary mapping integers to sorted lists, and binary search.

Code Solutions

# Python solution
import bisect

def countSubstrings(word, k):
    n = len(word)
    vowels = set("aeiou")
    # Build prefix sum array: pre[i] = number of consonants in word[0..i-1]
    pre = [0]*(n+1)
    for i in range(1, n+1):
        # If the character is not a vowel, it is a consonant
        pre[i] = pre[i-1] + (0 if word[i-1] in vowels else 1)
    
    # Build dictionary mapping a prefix consonant count value to sorted list of indices i where pre[i] has that value.
    pre_index_map = {}
    for i, val in enumerate(pre):
        if val not in pre_index_map:
            pre_index_map[val] = []
        pre_index_map[val].append(i)
    
    # Initialize last seen positions for vowels
    vowelLast = {v: -1 for v in vowels}
    res = 0
    # Iterate over each ending index r of the substring
    for r, ch in enumerate(word):
        if ch in vowels:
            vowelLast[ch] = r  # update latest occurrence for this vowel
        
        # Check if all vowels have appeared at least once in word[0..r]
        if any(vowelLast[v] == -1 for v in vowels):
            continue
        # validLimit: any valid starting index i must be <= the earliest (minimum) vowel last occurrence.
        validLimit = min(vowelLast.values())
        # Compute target prefix value that the starting index must have.
        target = pre[r+1] - k
        # If target is not in our mapping, no starting indices qualify.
        if target not in pre_index_map:
            continue
        indices = pre_index_map[target]
        # Count how many indices in 'indices' are <= validLimit using binary search.
        count = bisect.bisect_right(indices, validLimit)
        res += count
    return res

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