Count Vowel Substrings of a String — LeetCode 2062 Python Solution

The problem

A substring is a contiguous (non-empty) sequence of characters within a string. A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Example

Input

word = "aeiouu"

Output

2

Explanation

The vowel substrings of word are as follows (underlined):

Python solution

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        s = set("aeiou")
        ans, n = 0, len(word)
        for i in range(n):
            t = set()
            for c in word[i:]:
                if c not in s:
                    break
                t.add(c)
                ans += len(t) == 5
        return ans

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2062. Count Vowel Substrings of a String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems