#1878Time: O(N^3), where N is the length of the string. The two nested loops run in O(N^2), and for each of the O(N^2) substrings, we iterate through it to check its validity, which can take up to O(N) time.Space: O(N), where N is the length of the string. This is because `word.substring(i, j + 1)` can create a new string of length up to N. The `HashSet` uses O(1) space as there are only 5 vowels.4 companies
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 inword.
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible substring of the input word and then checking if each substring meets the criteria of a "vowel substring". A substring is valid if it contains only vowels and includes all five vowels ('a', 'e', 'i', 'o', 'u').
Algorithm
Initialize a counter count to 0.
Use two nested loops to generate all substrings. The outer loop with index i determines the start of the substring, and the inner loop with index j determines the end.
For each substring s = word.substring(i, j + 1):
Check if s is a valid vowel substring using a helper function isVowelSubstring(s).
The helper function isVowelSubstring(s) will:
Iterate through each character of s. If any character is a consonant, return false.
Use a HashSet to keep track of the unique vowels present in s.
After checking all characters, if the size of the HashSet is exactly 5, return true. Otherwise, return false.
If isVowelSubstring(s) returns true, increment the count.
After checking all substrings, return count.
Walkthrough
The algorithm iterates through all possible start and end points to define a substring. For each generated substring, it performs a two-part check. First, it verifies that every character in the substring is a vowel. If this holds, it then checks if the set of unique vowels in the substring contains all five required vowels. This is the most straightforward but also the least efficient way to solve the problem.
1import java.util.HashSet;2import java.util.Set;34class Solution {5 public int countVowelSubstrings(String word) {6 int count = 0;7 int n = word.length();8 for (int i = 0; i < n; i++) {9 for (int j = i; j < n; j++) {10 String sub = word.substring(i, j + 1);11 if (isVowelSubstring(sub)) {12 count++;13 }14 }15 }16 return count;17 }1819 private boolean isVowel(char c) {20 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';21 }2223 private boolean isVowelSubstring(String s) {24 Set<Character> vowels = new HashSet<>();25 for (char c : s.toCharArray()) {26 if (!isVowel(c)) {27 return false;28 }29 vowels.add(c);30 }31 return vowels.size() == 5;32 }33}
Complexity
Time
O(N^3), where N is the length of the string. The two nested loops run in O(N^2), and for each of the O(N^2) substrings, we iterate through it to check its validity, which can take up to O(N) time.
Space
O(N), where N is the length of the string. This is because `word.substring(i, j + 1)` can create a new string of length up to N. The `HashSet` uses O(1) space as there are only 5 vowels.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient due to the cubic time complexity.
It might be too slow for larger inputs, though it passes for the given constraints (N <= 100).
This approach improves upon the brute-force method by avoiding the creation of new substrings and re-checking characters repeatedly. Instead of generating and checking each substring from scratch, we can check the properties of substrings starting at a fixed position i in a single, more efficient pass.
Algorithm
Initialize a counter count to 0.
Iterate through the string with an outer loop using index i from 0 to N-1. This i will be the starting point of our potential substrings.
Inside the outer loop, initialize a HashSet to store the vowels encountered for substrings starting at i.
Start an inner loop with index j from i to N-1. This j will be the ending point.
For each character word.charAt(j):
Check if it's a vowel. If it's a consonant, then no further substring starting at i and ending at or after j can be a vowel-only substring. So, break the inner loop.
If it's a vowel, add it to the HashSet.
Check if the size of the HashSet is 5. If it is, we have found a valid vowel substring word.substring(i, j + 1), so we increment count.
Walkthrough
We use nested loops where the outer loop fixes the starting point i of a substring. The inner loop extends the substring by one character at a time, moving from i to the end of the string. For each starting point i, we maintain a HashSet of vowels. As we extend the substring to the right with index j, we add the new character to the set. If we encounter a consonant, we know that no further extension from i will result in a valid vowel-only substring, so we can break the inner loop and move to the next starting position. If the character is a vowel, we add it to our set and check if the set's size has reached 5. If it has, we've found a valid vowel substring and increment our counter.
1import java.util.HashSet;2import java.util.Set;34class Solution {5 public int countVowelSubstrings(String word) {6 int count = 0;7 int n = word.length();8 Set<Character> vowels = new HashSet<>();9 vowels.add('a');10 vowels.add('e');11 vowels.add('i');12 vowels.add('o');13 vowels.add('u');1415 for (int i = 0; i < n; i++) {16 Set<Character> foundVowels = new HashSet<>();17 for (int j = i; j < n; j++) {18 char c = word.charAt(j);19 if (!vowels.contains(c)) {20 break; // Not a vowel, so break the inner loop21 }22 foundVowels.add(c);23 if (foundVowels.size() == 5) {24 count++;25 }26 }27 }28 return count;29 }30}
Complexity
Time
O(N^2). We have two nested loops. The operations inside the inner loop (HashSet add, checking size) take constant time on average.
Space
O(1). The `HashSet` used to track found vowels stores at most 5 distinct characters, which is constant space.
Trade-offs
Pros
More efficient than the O(N^3) approach.
Avoids expensive substring creation in each iteration.
Cons
Still not the most optimal solution as it has a quadratic time complexity.
The most efficient approach uses a sliding window technique. The core idea is to first recognize that any valid vowel substring must be entirely contained within a contiguous block of vowels. Consonants act as natural boundaries. We can therefore solve the problem for each vowel-only block and sum the results. To count substrings with exactly 5 distinct vowels within a block, we use a clever trick: calculate the number of substrings with at most 5 distinct vowels and subtract the number of substrings with at most 4 distinct vowels.
Algorithm
The main problem is broken down: count substrings with exactly 5 distinct vowels that only contain vowels.
This can be rephrased as:
1(count of substrings with at most 5 distinct vowels) - (count of substrings with at most 4 distinct vowels)
.
We first iterate through the input string to identify contiguous blocks of vowels. Consonants act as separators.
For each vowel-only block, we apply a helper function, countAtMostK(word, start, end, k), twice: once for k=5 and once for k=4.
The countAtMostK(word, start, end, k) function uses a sliding window:
Initialize count = 0, left = start, and a frequency map for vowels.
Iterate from start to end with a right pointer.
Add word.charAt(right) to the window and update the frequency map and the count of distinct vowels.
If the number of distinct vowels exceeds k, shrink the window from the left by incrementing the left pointer and updating the map until the condition is met again.
For each right, the number of valid substrings ending at right is right - left + 1. Add this to the total count.
The result for a vowel block is countAtMostK(block, 5) - countAtMostK(block, 4).
Sum these results for all vowel blocks to get the final answer.
Walkthrough
This method provides a linear-time solution. We iterate through the string with a pointer i. If word.charAt(i) is a consonant, it marks the end of a potential vowel-only segment. We then calculate the number of valid substrings within the segment from the last consonant (or the beginning of the string) to i-1. This calculation is done by calling a helper function atMost(k) which counts substrings with at most k distinct vowels. The final count for the segment is atMost(5) - atMost(4). The atMost(k) helper function itself uses a sliding window (left, right pointers) and a frequency map to efficiently count the substrings in linear time.
1import java.util.HashMap;2import java.util.Map;34class Solution {5 public int countVowelSubstrings(String word) {6 int totalVowelSubstrings = 0;7 int lastConsonant = -1;8 for (int i = 0; i < word.length(); i++) {9 if (!isVowel(word.charAt(i))) {10 lastConsonant = i;11 }12 // For a window ending at i, we need a starting point j such that13 // word[j...i] is a valid vowel substring.14 // This is hard to count directly. Instead, we use an inclusion-exclusion principle.15 // We find a window [j, i] that contains only vowels.16 // Then count substrings in word[j...i] with exactly 5 vowels.17 // This is equal to (count of substrings with at most 5 vowels) - (count of substrings with at most 4 vowels).18 }19 return atMost(word, 5) - atMost(word, 4);20 }2122 private int atMost(String s, int k) {23 int count = 0;24 int left = 0;25 Map<Character, Integer> freq = new HashMap<>();26 for (int right = 0; right < s.length(); right++) {27 char c = s.charAt(right);28 if (!isVowel(c)) {29 // Reset window if a consonant is found30 left = right + 1;31 freq.clear();32 continue;33 }3435 freq.put(c, freq.getOrDefault(c, 0) + 1);3637 while (freq.size() > k) {38 char leftChar = s.charAt(left);39 freq.put(leftChar, freq.get(leftChar) - 1);40 if (freq.get(leftChar) == 0) {41 freq.remove(leftChar);42 }43 left++;44 }45 // For the window [left, right], all substrings ending at right are valid.46 // The number of such substrings is (right - left + 1).47 count += (right - left + 1);48 }49 return count;50 }5152 private boolean isVowel(char c) {53 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';54 }55}
Complexity
Time
O(N). The `atMost` function processes each character of the string at most twice (once by the `right` pointer, once by the `left` pointer). Since we call it twice, the complexity is O(N) + O(N) = O(N).
Space
O(1). The frequency map for vowels uses constant space as there are at most 5 keys.
Trade-offs
Pros
Optimal time complexity.
Efficient and scalable for larger inputs.
Cons
The logic is more complex to understand and implement compared to brute-force approaches.
Solutions
Solution
1class Solution {2public3 int countVowelSubstrings(String word) {4 int n = word.length();5 int ans = 0;6 for (int i = 0; i < n; ++i) {7 Set<Character> t = new HashSet<>();8 for (int j = i; j < n; ++j) {9 char c = word.charAt(j);10 if (!isVowel(c)) {11 break;12 }13 t.add(c);14 if (t.size() == 5) {15 ++ans;16 }17 }18 }19 return ans;20 }21private22 boolean isVowel(char c) {23 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';24 }25}
1class Solution {2public:3 int countVowelSubstrings(string word) {4 int ans = 0;5 int n = word.size();6 for (int i = 0; i < n; ++i) {7 unordered_set<char> t;8 for (int j = i; j < n; ++j) {9 char c = word[j];10 if (!isVowel(c))11 break;12 t.insert(c);13 ans += t.size() == 5;14 }15 }16 return ans;17 }18 bool isVowel(char c) {19 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';20 }21};
1class Solution:2 def countVowelSubstrings(self, word: str) -> int: n = len(word) s = set('aeiou') return sum(set(word[i: j]) == s for i in range(n) for j in range(i + 1, n + 1))
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
