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"
Example 4:
Input: word = "bbaeixoubb" Output: 0 Explanation: The only substrings that contain all five vowels also contain consonants, so there are no vowel substrings.
Constraints:
1 <= word.length <= 100
word
consists of lowercase English letters only.
Solution 1: Brute Force
Time complexity: O(n2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int countVowelSubstrings(string_view word) { const int n = word.size(); auto check = [&](string_view s) { set<int> seen; string vowels {"aeiou"}; for (char c : s) { if (vowels.find(c) == string::npos) return false; seen.insert(c); } return seen.size() == 5; }; int ans = 0; for (int i = 0; i < n; ++i) for (int l = 5; i + l <= n; ++l) if (check(word.substr(i, l))) ++ans; return ans; } }; |
Solution 2: Sliding Window / Three Pointers
Maintain a window [i, j] that contain all 5 vowels, find k s.t. [k + 1, i] no longer container 5 vowels.
# of valid substrings end with j will be (k – i).
##aeiouaeioo##
..i....k...j..
i = 3, k = 8, j = 12
Valid substrings are:aeiouaeioo
.eiouaeioo
..iouaeioo
...ouaeioo
....uaeioo
8 – 3 = 5
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int countVowelSubstrings(string_view word) { constexpr string_view vowels{"aeiou"}; int ans = 0; unordered_map<char, int> m; for (char c : vowels) m[c] = 0; for (size_t i = 0, j = 0, k = 0, v = 0; j < word.size(); ++j) { if (m.count(word[j])) { v += (++m[word[j]] == 1); while (v == 5) v -= (--m[word[k++]] == 0); ans += k - i; } else { for (char c : vowels) m[c] = 0; v = 0; i = k = j + 1; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment