algoadvance

You are given a string word. A substring is a contiguous (non-empty) sequence of characters within the string. A vowel substring is a substring that consists only of vowels (a, e, i, o, u) and has all five vowels present at least once.

Write a function countVowelSubstrings(word: str) -> int that returns the number of vowel substrings in word.

Clarifying Questions

  1. What characters can the input string contain?
    • The input string can contain lowercase English letters only.
  2. Can the input string be empty?
    • No, the problem specifies a non-empty string.
  3. What is the maximum length of the input string?
    • This isn’t explicitly stated but typically, problems like these assume reasonable constraints (n ≤ 10^4 or similar).
  4. Do vowel substrings need to contain unique instances of all five vowels or just at least one instance of each?
    • Each vowel substring must contain at least one instance of ‘a’, ‘e’, ‘i’, ‘o’, ‘u’.

Strategy

  1. Identify Vowel Substrings:
    • Traverse the string and identify substrings made up entirely of vowels.
  2. Substrings with All Vowels:
    • For each starting position of a vowel substring, continue to expand until the substring contains all five vowels.
  3. Sliding Window Approach:
    • Use a sliding window technique to count and check substrings efficiently.

Code

Here’s a Python solution implementing the above strategy:

def countVowelSubstrings(word: str) -> int:
    vowels = set('aeiou')
    total_count = 0
    n = len(word)

    for start in range(n):
        if word[start] in vowels:
            seen_vowels = set()
            for end in range(start, n):
                if word[end] in vowels:
                    seen_vowels.add(word[end])
                    if len(seen_vowels) == 5:
                        total_count += 1
                else:
                    break

    return total_count

Time Complexity

Overall, the worst-case time complexity is (O(n^2)), where n is the length of the input string word.

This solution should be efficient enough for typical constraints found in coding interview problems.

Try our interview co-pilot at AlgoAdvance.com