Count Vowel Substrings of a String
Count Vowel Substrings of a String is a easy arrays & hashing problem solved with the sliding window · variable pattern.
The best approach, optimal (last positions, one pass), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every start, extend until a consonant) up.
Problem
A vowel substring is a non-empty contiguous part of a string that contains only the vowels a, e, i, o and u, and contains each of those five vowels at least once.
Given a lowercase string word, return how many of its substrings are vowel substrings. Substrings at different positions are counted separately, even if they spell the same text.
Examples
Example 1
- Input
word = "xaeioub"- Output
1- Why
- Only "aeiou" is made of vowels alone and uses all five of them.
Example 2
- Input
word = "uaeioua"- Output
6- Why
- The vowel substrings with all five vowels are "uaeio", "uaeiou", "uaeioua", "aeiou", "aeioua" and "eioua".
Example 3
- Input
word = "aeixou"- Output
0- Why
- The consonant x splits the word, and neither side has all five vowels.
Constraints
1 <= word.length <= 100wordconsists of lowercase English letters only.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (every start, extend until a consonant) | O(n²) | O(1) |
| Optimal (last positions, one pass) | O(n) | O(1) |
1Brute force (every start, extend until a consonant)
O(n²)Each of n starts extends at most n characters.O(1)The set holds at most 5 letters.For each start index, extend the end to the right while the characters are vowels, keeping a set of vowels seen. Every time the set has all five vowels, the current substring counts.
- For each start i, clear a set of seen vowels.
- Extend j from i while
word[j]is a vowel; add it to the set. - If the set has 5 vowels, add 1 to the answer.
- Stop extending at the first consonant.
class Solution {
public int countVowelSubstrings(String word) {
int n = word.length(), count = 0;
for (int i = 0; i < n; i++) {
Set<Character> seen = new HashSet<>();
for (int j = i; j < n; j++) {
char c = word.charAt(j);
if ("aeiou".indexOf(c) < 0) break;
seen.add(c);
if (seen.size() == 5) count++;
}
}
return count;
}
}class Solution:
def countVowelSubstrings(self, word: str) -> int:
n, count = len(word), 0
for i in range(n):
seen = set()
for j in range(i, n):
c = word[j]
if c not in "aeiou":
break
seen.add(c)
if len(seen) == 5:
count += 1
return countclass Solution {
public:
int countVowelSubstrings(string word) {
int n = word.size(), count = 0;
string vowels = "aeiou";
for (int i = 0; i < n; i++) {
set<char> seen;
for (int j = i; j < n; j++) {
char c = word[j];
if (vowels.find(c) == string::npos) break;
seen.insert(c);
if (seen.size() == 5) count++;
}
}
return count;
}
};function countVowelSubstrings(word) {
const n = word.length;
let count = 0;
for (let i = 0; i < n; i++) {
const seen = new Set();
for (let j = i; j < n; j++) {
const c = word[j];
if (!"aeiou".includes(c)) break;
seen.add(c);
if (seen.size === 5) count++;
}
}
return count;
}2Optimal (last positions, one pass)
O(n)One pass, with a constant five-way minimum at each step.O(1)Five last-seen positions and one consonant index.Scan the end index j once. Remember the index of the last consonant and, for each vowel, the last index where it appeared. A start i works for end j exactly when i is after the last consonant and i is at or before the last position of every vowel. So the number of valid starts is min(last[v]) - lastConsonant when that is positive.
- Set
lastCons = -1andlast[v] = -1for each of the five vowels. - For each j: if
word[j]is a consonant, setlastCons = jand continue. - Otherwise set
last[word[j]] = jand letm = min(last[a], last[e], last[i], last[o], last[u]). - If
m > lastCons, addm - lastConsto the answer.
class Solution {
public int countVowelSubstrings(String word) {
String vowels = "aeiou";
int[] last = { -1, -1, -1, -1, -1 };
int lastCons = -1, count = 0;
for (int j = 0; j < word.length(); j++) {
int v = vowels.indexOf(word.charAt(j));
if (v < 0) {
lastCons = j;
continue;
}
last[v] = j;
int m = Integer.MAX_VALUE;
for (int p : last) m = Math.min(m, p);
if (m > lastCons) count += m - lastCons;
}
return count;
}
}class Solution:
def countVowelSubstrings(self, word: str) -> int:
vowels = "aeiou"
last = [-1] * 5
last_cons, count = -1, 0
for j, ch in enumerate(word):
v = vowels.find(ch)
if v < 0:
last_cons = j
continue
last[v] = j
m = min(last)
if m > last_cons:
count += m - last_cons
return countclass Solution {
public:
int countVowelSubstrings(string word) {
string vowels = "aeiou";
int last[5] = {-1, -1, -1, -1, -1};
int lastCons = -1, count = 0;
for (int j = 0; j < (int)word.size(); j++) {
size_t pos = vowels.find(word[j]);
if (pos == string::npos) {
lastCons = j;
continue;
}
last[pos] = j;
int m = INT_MAX;
for (int p : last) m = min(m, p);
if (m > lastCons) count += m - lastCons;
}
return count;
}
};function countVowelSubstrings(word) {
const vowels = "aeiou";
const last = [-1, -1, -1, -1, -1];
let lastCons = -1, count = 0;
for (let j = 0; j < word.length; j++) {
const v = vowels.indexOf(word[j]);
if (v < 0) {
lastCons = j;
continue;
}
last[v] = j;
const m = Math.min(...last);
if (m > lastCons) count += m - lastCons;
}
return count;
}Edge cases to test
- Word shorter than 5 characters
- No consonants at all
- Consonants splitting the word into vowel blocks that are each missing a vowel
- Repeated vowels, so many substrings share the same set
Hints
Hint 1
A counted substring may not contain any consonant, and must contain each of a, e, i, o, u at least once.
Hint 2
Fix a start and extend the end; stop as soon as you hit a consonant.
Hint 3
For a linear scan: for each end, the valid starts lie after the last consonant and at or before the earliest of the last positions of the five vowels.
FAQ
What is the best time complexity for Count Vowel Substrings of a String?
Optimal (last positions, one pass) runs in O(n) time and O(1) extra space. One pass, with a constant five-way minimum at each step.
Which pattern does Count Vowel Substrings of a String use?
It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.
Is there a brute force solution for Count Vowel Substrings of a String?
Yes. Brute force (every start, extend until a consonant) takes O(n²) time and O(1) space. For each start index, extend the end to the right while the characters are vowels, keeping a set of vowels seen.
Which edge cases should I test for Count Vowel Substrings of a String?
Word shorter than 5 characters; No consonants at all; Consonants splitting the word into vowel blocks that are each missing a vowel; Repeated vowels, so many substrings share the same set.