Skip to content

2062. Count Vowel Substrings of a String

Description

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.

Given a string word, return the number of vowel substrings in word.

 

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

 

Constraints:

  • 1 <= word.length <= 100
  • word consists of lowercase English letters only.

Solutions

Solution 1: Brute Force Enumeration + Hash Table

Thinking

With \(n \le 100\) all \(O(n^2)\) substrings are cheap. A vowel substring uses only vowels and all five of them. Fix the left end and grow right; a consonant kills that left end; a set of size \(5\) scores one.

A hash set stores vowels seen in the current span.

We can enumerate the left endpoint \(i\) of the substring. For the current left endpoint, maintain a hash table to record the vowels that appear in the current substring. Then enumerate the right endpoint \(j\). If the character at the current right endpoint is not a vowel, break the loop. Otherwise, add the character at the current right endpoint to the hash table. If the number of elements in the hash table is \(5\), it means the current substring is a vowel substring, and increment the result by \(1\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(C)\). Here, \(n\) is the length of the string \(word\), and \(C\) is the size of the character set, which is \(5\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countVowelSubstrings(String word) {
        int n = word.length();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            Set<Character> t = new HashSet<>();
            for (int j = i; j < n; ++j) {
                char c = word.charAt(j);
                if (!isVowel(c)) {
                    break;
                }
                t.add(c);
                if (t.size() == 5) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countVowelSubstrings(string word) {
        int ans = 0;
        int n = word.size();
        for (int i = 0; i < n; ++i) {
            unordered_set<char> t;
            for (int j = i; j < n; ++j) {
                char c = word[j];
                if (!isVowel(c)) break;
                t.insert(c);
                ans += t.size() == 5;
            }
        }
        return ans;
    }

    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func countVowelSubstrings(word string) int {
    ans, n := 0, len(word)
    for i := range word {
        t := map[byte]bool{}
        for j := i; j < n; j++ {
            c := word[j]
            if !(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                break
            }
            t[c] = true
            if len(t) == 5 {
                ans++
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function countVowelSubstrings(word: string): number {
    let ans = 0;
    const n = word.length;
    for (let i = 0; i < n; ++i) {
        const t = new Set<string>();
        for (let j = i; j < n; ++j) {
            const c = word[j];
            if (!(c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u')) {
                break;
            }
            t.add(c);
            if (t.size === 5) {
                ans++;
            }
        }
    }
    return ans;
}

Comments